[C++]01背包問題

01背包問題：

有n個重量和價值分别為wi,vi的物品。從這些物品中挑選出總重量不超過W的物品，求所有挑選方案中價值總和的最大值

輸入格式：

n

w v

W

輸出格式：

價值總和最大值

輸入：

4

2 3

1 2

3 4

2 2

5

輸出：

7

解題思路：對每個物品有兩種選擇，選或者不選。選擇該物品的話，總價值會增加，剩下的可載重量會減少，如果不選擇，則兩者不會變化。用遞歸可以解出，不過會有重複計算，為了降低複雜度，可用記憶化搜尋–動态規劃

#include<iostream>
#include<algorithm>
using namespace std;

const int maxn = 1000;

int n;
int w[maxn];
int v[maxn];
int W;

int dp[maxn+1][maxn+1];

int main(){
    cin>>n;
    for(int i = 0; i<n; i++){
        cin>>w[i]>>v[i];
    }
    cin>>W;
    for(int i = 0; i<n; i++){
        for(int j = 0; j<=W; j++){
            if(w[i] > j)
                dp[i+1][j] = dp[i][j];
            else {
                dp[i+1][j] = max(dp[i][j] , dp[i][j-w[i]] + v[i]); 
            }
        }
    }
    
    cout<<dp[n][W]<<endl;

    
    return 0;
}