POJ-2184 （01背包的负数处理）

74 阅读 0 评论 49 点赞

我是靠谱客的博主优秀毛豆，最近开发中收集的这篇文章主要介绍POJ-2184 （01背包的负数处理），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

i	TS[i]	TF[i]
1	-5	7
2	8	-6
3	-2	3

如图所示，要求TS[i]和TF[i]的和最大，但是TS[i]的和不能为负数，TF[i]的和也不能为负数。输出最终的最大的和。
我们可以把他看成01背包的问题。我们可以假设TS[i]是正数，（其实也不用假设，即便为负数，我们也只是需要移动区间而已，从而使得TS[i]为正）。也就是求在花费TS[i]的基础上，获取的TF[i]的价值。
比如说下边这个例子：

TS[i]	TF[i]
2	3
6	-7

我们可以写出dp[2]=3; dp[8]=4;就是这个道理，最后再把8+4=12就行了。
我们令dp[100000]=0，因为其他的值都有可能是负数，所以我们把其他的都赋值为负无穷。
以100000作为原点，这样dp括号里的容量就不会为负数了。

如同01背包一样，如果TS[i]是正数，则有如下循环：
for(i=0;i<n;i++)
   {
       if(TS[i]>0)
           for(j=200000;j>=TS[i];j--)
           dp[j]=max(dp[j],dp[j-TS[i]]+TF[i]);
}
如果是负数，则是：
for(i=0;i<n;i++)
   {
       if(TS[i]<=0)
   for(j=0;j-TS[i]<=200000;j++)
           dp[j]=max(dp[j],dp[j-TS[i]]+TF[i]);
   }

有这样几个问题：

为什么TS[i]为负数是要用正序循环
在标准的01背包里，我们看见j>j-TS[i]，也就是说我们要想求dp[j]，我们必须用到上一层的dp[j]和dp[j-TS[i]]，也就是要用到上一层的他自己dp[j]与自变量j-TS[i]小于自己的[j]的dp[j-TS[i]],如果正序的话，dp[j-TS[i]]就会被破坏掉。
同样的，如果TS[i]是负数，j-TS[i]>j,如果我们要求dp[j],我们要用到上一层的dp[j]与上一层的自变量j-TS[i]大于j的dp[j-TS[i]],如果按照逆序循环,dp[j-TS[i]]会被破坏掉。
可不可以把TS[i]是负数时改成如下：

 for(j-TS[i]=200000;j>=0;j--)
           dp[j]=max(dp[j],dp[j+TS[i]]+TF[i]);

这也是不可以的。
因为当TS[i]是负数的时候，dp[j]括号中的这个容量应该由大容量推来。比如说你要算dp[100003],那你就应该由dp[100004]等等推来。也就是说你要保证max中的后边的dp括号中的自变量要大于前边的dp。
下面给出文章开头例子的计算过程：

第一次，s[0]=-5<0;
可得
{
dp[99995]=7;
dp[100000]=0;
}
第二次，s[1]=8>0
{
dp[99995]=7;
dp[100000]=0;
dp[100003]=1
};
第三次，s[2]<0;
{
dp[99993]=10;
dp[99995]=7;
dp[100003]=1;
dp[100001]=4;
}

``
最后说明求总和的最大值：

因为我们要保证TS[i]和TF[i]的和分别都大于0，TS[i]的和用dp[]括号里的值是否大于100000来保证，只要大于100000，说明TS[i]的总和没有是负数。这个是显而易见的，比如说dp[99995]=7,代表在TS[i]的和是-5的情况下，所获的最大价值是7.
再就是保证TF[i]的和大于0，这个通过dp[]的值来保证，值大于0说明TF[i]总和大于0.
所以我们利用如下循环，就可以求出总和的最大值：

 for(i=100000;i<=200000;i++)
    {
        if(dp[i]>=0)
            l=max(l,i+dp[i]-100000);
    }

l便是最终答案。
下面是POJ-2184代码：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int inf=0x3f3f3f3f;
int dp[200001],TS[200001],TF[200001];
int main()
{
    int n,i,j,ans=0;
    memset(dp,-inf,sizeof(dp));
    dp[100000]=0;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>TS[i]>>TF[i];
    }
    for(i=1;i<=n;i++)
    {
        if(TS[i]>=0)
        for(j=200000;j>=TS[i];j--)
            dp[j]=max(dp[j],dp[j-TS[i]]+TF[i]);
        else
        for(j=0;j-TS[i]<=200000;j++)
            dp[j]=max(dp[j],dp[j-TS[i]]+TF[i]);
    }
    for(i=100000;i<=200000;i++)
    {
        if(dp[i]>=0)
            ans=max(ans,dp[i]+i-100000);
    }
    cout<<ans<<endl;
}