poj2184 01背包变形,价值为可为负数

时间:2023-03-09 09:42:48
poj2184 01背包变形,价值为可为负数

题目链接:http://poj.org/problem?id=2184

题意:每行给出si和fi,代表牛的两个属性,然后要求选出几头牛,满足S与F都不能为负数的条件下,使S与F的和最大。

tips:动态规划中状态维和值是可以相互转化的。状态维过多,效率低的时候,可以把将其转化为数组值;同理,数组值不唯一无法规划时,可以增加状态维使状态更详细。

这道题有两个值,把其中一个值转换为状态维。注意价值和体积都可以为负数的时候是怎么求。

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
const int INF=0x3f3f3f3f;
const int maxn=2e5+;
const int x=1e5;
const int y=2e5; int dp[maxn];
int a[],b[]; int main()
{
int N;
while(scanf("%d",&N)==)
{
for(int i=; i<=N; i++)
scanf("%d%d",&a[i],&b[i]);
for(int i=; i<maxn; i++) ///因为是用数组的维数代表价值,所以要求必须装满
dp[i]=-INF; ///这里不可以用-1来标记,因为价值可能是负的
dp[x]=; ///刚好什么都没装的状态
for(int i=; i<=N; i++)
{
if(a[i]>){
for(int j=y; j>=a[i]; j--)
if(dp[j-a[i]]>-INF)
dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
}
else{
for(int j=; j<=y+a[i]; j++)
if(dp[j-a[i]]>-INF)
dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
}
}
int ans=-INF;
for(int i=x; i<=y; i++)
if(dp[i]>=) ans=max(ans,i-x+dp[i]);
printf("%d\n",ans);
}
return ;
}