放牧代码和思想
专注自然语言处理、机器学习算法
    正处于一个非常忙的阶段,抱歉不会经常回应任何联络

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版)》

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机