POJ 2184（01背包）（负体积）

http://poj.org/problem?id=2184

http://blog.csdn.net/liuqiyao_01/article/details/8753686

对于负体积问题，可以先定义一个“零点”shift，将dp[shift]设为0，其他都设为-INF。

然后负体积从0往maxn+cost更新，正体积从maxn往shift更新。

最后从shift到maxn中找最大值，shift以下的值不会被遍历到

#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <stack>
using namespace std;#define MEM(a,b) memset(a,b,sizeof(a))
#define pf printf
#define sf scanf
#define debug printf("!\n")
#define INF (0x3f3f3f3f)
#define MAX(a,b) a>b?a:b
#define blank pf("\n")
#define LL long long
#define ep 1e-6const int shift = ;
const int MAXN  = ;
const int MAXM = ;int dp[MAXN];int ci[MAXM];//容量
int wi[MAXM];//价值
int n,V,i,j,v,t,sum;
double G;void zeroOnePack(int cost,int weight)
{
          if(cost>=)
          {
                    for(v = MAXN-;v>=cost;v--)
                    {
                              dp[v] =MAX(dp[v],dp[v-cost]+weight);
                    }
          }
          else
          {
                    for(v = ;v<MAXN+cost;v++)
                    {
                              dp[v] =MAX(dp[v],dp[v-cost]+weight);
                    }
          }
}int main()
{
          while(sf("%d",&n)!=EOF)
          {                    MEM(dp,-INF);
                    MEM(wi,);                    for(i = ;i<n;i++)
                    {
                              sf("%d",&ci[i]);
                              sf("%d",&wi[i]);
                    }                    dp[shift] = ;                    for(i = ;i<n;i++)
                    {
                              zeroOnePack(ci[i],wi[i]);
                    }                    int ans = -INF;                    for(i = shift;i<MAXN;i++)
                    {
                              if(dp[i]>= && (i-shift+dp[i])>ans)
                                        ans = i-shift+dp[i];
                    }
                    pf("%d\n",ans);          }
    return ;
}
/*
5
-5 7
8 -6
6 -3
2 1
-8 -5
*/