POJ 2184 Cow Exhibition (带负值的01背包)

时间:2021-12-03 04:35:23

题意:给你N(N<=100)只牛,每只牛有一个智慧值Si和一个活泼值Fi,现在要从中找出一些来,使得这些牛智慧值总和S与活泼值总和F之和最大,且F和S均为正。Si和Fi范围在-1000到1000之间。

思路:

可以把S当体积,F当价值做01背包。但是注意是S可为负,所以整体加100000,然后要注意DP顺序,S为负是要顺序,为正时逆序。注意DP时的范围,凡是可能影响的都要包括。

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 110;
int dp[200010];
int value[MAXN];
int weight[MAXN];
int nKind;
int main()
{
int k = 100000;
while (scanf("%d", &nKind) != EOF)
{
for (int i = 0; i < nKind; i++)
{
scanf("%d%d", &value[i], &weight[i]);
}
for (int i = 0; i <= 200000; i++)dp[i] = -INF;//因为有负数
dp[k] = 0;//原点开始
for (int i = 0; i<nKind; i++)
{
if (value[i]>0)//正的是逆序
{
for (int j = 200000; j >= value[i]; j--)//注意范围
if (dp[j - value[i]] > -INF)
dp[j] = max(dp[j], dp[j - value[i]] + weight[i]);
}
else//负的是顺序
{
for (int j = 0; j <= 200000 + value[i]; j++)//注意范围
if (dp[j - value[i]] > -INF)
dp[j] = max(dp[j], dp[j - value[i]] + weight[i]);
}
}
int ans = 0;
for (int i = 100000; i <= 200000; i++)//s和为正
if (dp[i] >= 0 && dp[i] + i - 100000 > ans)//f和为正
ans = dp[i] + i - 100000;
printf("%d\n", ans);
}
return 0;
}