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;
}