hdu 2602 01背包

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個背包，結果當然就是從第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;
}