题意：有很多牛，每只牛有一个智商和幽默度，要选出一些牛，智商加幽默度总和最大，其中智商总和和幽默度总和都不能是负数。
mark：变种的01背包，可以把智商看成体积，幽默度看成价值，那么就转换成求体积和价值都为正值的最大值的01背包了。
由于有负数，所以可以每个体积+1000，然后开一个数组记录用该体积得到最大值时用了多少个1000.
dp方程：ans=max(dp[j]+j-cnt[j]*1000)
dp[j]表示体积为j时得到的最大价值，也就是智商为j使最大的幽默度。
转移条件：dp[j]-cnt[j]*1000<dp[j-v[i]]+w[i]-cnt[j-v[i]]*1000
首先计算出数据的范围：
一共100组数，从-1000到1000，那么体积的范围就是-100*1000到100*1000。
平移之后我们要处理的数据范围就在0到200000，新的原点变成100000。
#include<cstdio>
#include<iostream>
#include<cstring>
#define INF 0xffffff
#define N 1000
#define MAX 200010
using namespace std;
int dp[MAX],cnt[MAX];
int v[110],w[110],sum;
int main()
{
int n,ans;
while(scanf("%d",&n)!=EOF)
{
sum=0;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&v[i],&w[i]);
if(v[i]<0 && w[i]<0) //把v[i]和w[i]都为负的排除
{
i--;
n--;
continue;
}
v[i]+=1000; //把体积扩大1000,调整到正整数范围
sum+=v[i]; //计算转化后01背包的总容量
}
for(int i=1;i<=sum;i++) //由于是所有体积精确相加得到的总容量
dp[i]=-INF; //所以相当于一定要装满的01背包初始化
dp[0]=0;
memset(cnt,0,sizeof(cnt)); //cnt记录用该体积得到最大值时用了多少个1000.
for(int i=1;i<=n;i++)
{
for(int j=sum;j>=v[i];j--)
{
if(dp[j]-cnt[j]*N<dp[j-v[i]]+w[i]-(cnt[j-v[i]]+1)*N)
{
dp[j]=dp[j-v[i]]+w[i];
cnt[j]=cnt[j-v[i]]+1;
}
}
}
ans=-1;
for(int i=0;i<=sum;i++)
{
if(dp[i]>=0 && i-cnt[i]*N>=0)
ans=max(ans,dp[i]+i-cnt[i]*N);
}
printf("%d\n",ans);
}
return 0;
}
还有一种解法：
如果体积为负v-c[i]>v，从小到大遍历。
#include<cstdio>
#include<iostream>
#include<cstring>
#define INF 0xffffff
#define M 200000
#define MAX 200010
#define N 110
using namespace std;
int dp[MAX],w[N],v[N],ans;
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%d%d",&v[i],&w[i]);
for(int i=1;i<=M;i++)
dp[i]=-INF;
dp[100000]=0;
for(int i=1;i<=n;i++)
{
if(v[i]<0)
{
for(int j=0;j-v[i]<=M;j++)
{
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}
else
{
for(int j=M;j>=v[i];j--)
{
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}
}
ans=0;
for(int i=100000;i<=M;i++)
{
if(dp[i]>0)
ans=max(dp[i]+i-100000,ans);
}
printf("%d\n",ans);
}
return 0;
}
ans不能初始化为-1。
= =！