POJ Cow Exhibition 题解 《挑战程序设计竞赛(第2版)》

POJ 2184 Cow Exhibition

奶牛CJ：有N头奶牛想参加CJ，每头奶牛的智商分别为S_i，情商为F_i。欲挑出一群奶牛使得S之和与F之和都不为负数，且SF之和最大，求此最大值。

01背包

一开学又是工作又是赶寒假作业的，都没时间了(￣▽￣") 。

定义：

dp[i] = j i表示S值之和 + center，j表示F值之和的最大值，center是将坐标原点0往右移动center个单位，保证下标为正的某个值。

这题我只想到了01背包，不知道有没有更高效的算法。S为体积，F为价值。值得思考的是，01背包递推公式dp[j] = max(dp[j], dp[j – S[i]] + F[i]);下标是递减的，如果S是负值的话会导致重复计算，所以此时需要调转循环方向，让下标递增。注意，即使下标递增，它也依然是01背包，不要看着循环方向变了就想当然地认为是完全背包。完全背包的核心不同点是允许同一物品的重复计算，而这里显然没有重复计算！

然后是负值下标的处理，找一个合适的center值就行了，并不需要开那么大的值。

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
#include <algorithm>
#include <limits>
using namespace std;

int dp[1000 * 100 * 2 + 16];	// dp[i] = j 当S值之和为i - center时，F值之和j的最大值
int S[100 + 16];
int F[100 + 16];

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int N;
	cin >> N;
	// 真实范围锁定
	int center = 1000 * N;			// 中心点
	int range = center * 2 + 16;	// dp数组的利用范围，以center为中心，留了点空隙
	
	for (int i = 0; i < N; ++i)
	{
		cin >> S[i] >> F[i];
	}
	// 设定一个很小的值表示这个值无效
	memset(dp, 0x80, range * sizeof(int));
	// 没有考虑任何奶牛的时候，S之和为0，F值之和为0
	dp[center] = 0;
	// 整个是01背包
	for (int i = 0; i < N; ++i)
	{
		if (S[i] >= 0)
		{
			for (int j = range; j >= S[i]; --j)
			{
				dp[j] = max(dp[j], dp[j - S[i]] + F[i]);
			}
		}
		else
		{
			// 这不是完全背包，虽然它长得像，但没有发生重复计算
			// 所以不是完全背包
			for (int j = S[i]; j - S[i] < range; ++j)
			{
				dp[j] = max(dp[j], dp[j - S[i]] + F[i]);
			}
		}
	}

	int result = -range;
	for (int i = center; i < range; ++i)
	{
		if (dp[i] >= 0)
		{
			result = max(result, i - center + dp[i]);
		}
	}

	cout << result << endl;
	
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ Cow Exhibition 题解 《挑战程序设计竞赛(第2版)》