hdu 2602 01背包 - c++编程基础

背景：没有认真读题目条件，搞错输入顺序而wa了一次。自己做的第一道DP题，看了好久终于把背包九讲的01背包看懂了。

学习：

1.01背包的特点是：物品个数有限，切对于每一个物品可以选择放或者不放。其中的名称01，大概就是1（放）0（不放）的意思吧。

传统的背包写法使用二维数组，时间和空间都是O（VN），当把j由0.....n，换为n.....0之后空间优化为O(V),然后做了两点剪枝，这里解释一下剪枝的原理：

int min=max(list[1][i],v-sum(i,n-1));

分析：剪枝的具体方法如上就是将，j的循环下限为0，改成min。其中list[1][i]为当前选择物品（第i个物品）的花费，如果剩下的余下的体积已经小于list[1][i]，说明无论如何
也不可能选择第i个物品了，因为放不下，所以list[1][i].....0里还应该是上一次的内容，没有必要修改。其中v-sum(i,n-1)背包九讲留作思考题，笔者思考后如下解释：优化方案是：j必须大于等于v-sum(i,n-1),反方向来看：如果j小于v-sum(i,n-1)那么在第i个还没有放的时候，背包剩余容量足以放下第i到n个背包，结果当然就是从第i个到第n个全部都放总价值最大，无需判断，等价的说是，对于后面的每一个背包都有:F[j](不放）（F[j]= F[j-list[1][i]]）<= F[j-list[1][i]]+list[0][i],也就是每次都只需要选择右边的情况放第i个即可。

#include
  
   
using namespace std;
int list[2][1000],F[1001];
int sum(int i,int k){
    int ans=0;
    for(int j=i;j <= k;j++) ans+=list[1][j];
    return ans;
}

void dp(void){
     int v,n;
     cin >> n >> v;
     for(int i=0;i < v+1;i++) F[i]=0;
     for(int i=0;i < 2;i++)
         for(int j=0;j < n;j++)
             cin >> list[i][j];
     for(int i=0;i < n;i++){
         int min=max(list[1][i],v-sum(i,n-1));
         for(int j=v;j >= min;j--)
             F[j]=max(F[j],F[j-list[1][i]]+list[0][i]);
     }
     cout << F[v] << endl;
}


int main(void){
    int tests;
    cin >> tests;
    while (tests--) dp();
    return 0;
}