2023年8月1日发(作者：)

带负值的背包问题poj21841：选的⽜要保证两个属性和都要⼤于0。2.总和最⼤！想到什么。01背包，⼀个数要么不⽤，要么⽤，让价值最⼤。因为会出现负值，并且两个值均⼤于0 ，那么假设第⼀种属性已经⼤于0了--重新设置0点，让100*1000为0点，过了这个点，就说明选的第⼀个属性和⼤于0了，反之则没有。那么这时候就只需要管第⼆种的属性了。把第⼀种当做消耗来算，第⼆种属性来算价值（相当于只有花费a，才能得到b。因为a已经在坐标体现了。⼩于100000就为负，否则为正），进⾏DP。那么算出来就需要看dp值是否⼤于0了。01背包⼀维DP是倒序的。但是当a[i]为负数时，如果依旧倒序，反⽽递推式没有往⼩跑，因为是dp【j-a[i]】,a【i】为负，j-a反⽽变⼤。#include#include#include#include#include#include#include#include#include#include#include#include#define nl n<<1#define nr (n<<1)|1using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pairP;const int INF=0x3f3f3f3f;const ll INFF=0x3f3f3f3f3f3f3f3f;const double pi=acos(-1.0);const double eps=1e-9;const ll mod=1e9+7;int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0' | ch>'9') {if(ch=='-') f=-1;ch=getchar();} while(ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();} return x*f;}void Out(int aa){ if(aa>9) Out(aa/10); putchar(aa%10+'0');}int a[105],b[105];int dp[200010];int main(){ int n=read(); for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]); memset(dp,-INF,sizeof(dp)); dp[100000]=0; for(int i=1;i<=n;i++) { if(a[i]>0) { for(int j=200005;j>=a[i];j--) dp[j]=max(dp[j],dp[j-a[i]]+b[i]); } else else { for(int j=0;j<=200005+a[i];j++) dp[j]=max(dp[j],dp[j-a[i]]+b[i]); } } int ans=0; for(int i=100000;i<=200005;i++) { if(dp[i]>0) ans=max(ans,dp[i]+i-100000); } cout<

2023年8月1日发(作者：)

带负值的背包问题poj21841：选的⽜要保证两个属性和都要⼤于0。2.总和最⼤！想到什么。01背包，⼀个数要么不⽤，要么⽤，让价值最⼤。因为会出现负值，并且两个值均⼤于0 ，那么假设第⼀种属性已经⼤于0了--重新设置0点，让100*1000为0点，过了这个点，就说明选的第⼀个属性和⼤于0了，反之则没有。那么这时候就只需要管第⼆种的属性了。把第⼀种当做消耗来算，第⼆种属性来算价值（相当于只有花费a，才能得到b。因为a已经在坐标体现了。⼩于100000就为负，否则为正），进⾏DP。那么算出来就需要看dp值是否⼤于0了。01背包⼀维DP是倒序的。但是当a[i]为负数时，如果依旧倒序，反⽽递推式没有往⼩跑，因为是dp【j-a[i]】,a【i】为负，j-a反⽽变⼤。#include#include#include#include#include#include#include#include#include#include#include#include#define nl n<<1#define nr (n<<1)|1using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pairP;const int INF=0x3f3f3f3f;const ll INFF=0x3f3f3f3f3f3f3f3f;const double pi=acos(-1.0);const double eps=1e-9;const ll mod=1e9+7;int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0' | ch>'9') {if(ch=='-') f=-1;ch=getchar();} while(ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();} return x*f;}void Out(int aa){ if(aa>9) Out(aa/10); putchar(aa%10+'0');}int a[105],b[105];int dp[200010];int main(){ int n=read(); for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]); memset(dp,-INF,sizeof(dp)); dp[100000]=0; for(int i=1;i<=n;i++) { if(a[i]>0) { for(int j=200005;j>=a[i];j--) dp[j]=max(dp[j],dp[j-a[i]]+b[i]); } else else { for(int j=0;j<=200005+a[i];j++) dp[j]=max(dp[j],dp[j-a[i]]+b[i]); } } int ans=0; for(int i=100000;i<=200005;i++) { if(dp[i]>0) ans=max(ans,dp[i]+i-100000); } cout<