hdu 2602 01背包深入优化

背景：没有认真读题目条件，搞错输入顺序而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个背包，如果j<V-sum(j....n),不仅说明后面所以物品都可以放下(因为前面的子问题也是最优解，既然空间那么大，无后效性，肯定全部放下最好），也说明前面物品也可以放下，也就是，这些所有物品都可以放到背包中。综合来看，这个优化是用来避免一种特殊情况的：背包的总容量很大，以至于大到所有物品都可以放下。如果不采用这个优化，对于很大容量的背包，就会从那个很大的V值一直算到list[0][j]，显然会有很大的计算量。。         

#include<iostream>
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;
}