# 01 背包問題

## 問題描述:

有n件物品和一個容量為W的背包。第i件物品的重量是w[i]，價值是v[i]。求解將哪些物品裝入背包可使價值總和最大。

## 解:
直接用例子說明:
5個物品,（重量,價值）分別為：（5,12）,（4,3）,（7,10）,（2,3）,（6,6）

| 背包容量 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| -------- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 物品1+~5 | 0 | 0| 0 |0|0| 0| 6| 12 | 12| 15|15 | 18 | 22 | 22|25 | 25 |
| 物品1+~4 |0| 0 |3 | 3| 3 | 3 | 3| 12|12 |15 |15| 18 | 22 | 22 | 25 |25 |
| 物品1+2+3 | 0| 0 | 0| 0 |0 |0 |0 |12 | 12 | 15 | 15 | 15 |22 | 22| 22 |22 |
| 物品1+2 |0|0 | 0 | 0 | 3 |12 | 12|12 |12 | 15| 15| 15| 15 | 15 | 15 |15 |
| 物品1 |0|0|0|0|0|12|12|12|12|12|12|12|12|12|12|12|

for(int i = 1; i <= n; i++){
    for(int j = 0; j <= W; j++){
        if(j < w[i])    dp[i][j] = dp[i-1][j]; //沒辦法放，物品重量超過背包容量
        else dp[i][j] =  max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]);
                      // max(不放物品i  , 放物品i);
    }
}

優化空間複雜度:
以上方法的時間和空間複雜度均為O(VN)，其中時間複雜度已經不能再優化了，但空間複雜度卻可以優化到O(V)。因為其實根本不需要存二維陣列，只有最上面那一列是重要的。例如:放入物品1,2,3之後，物品1,物品1+2這兩列便可捨棄。這種二維轉一維的儲存方式稱為滾動數組。

for(int i = 1; i <= n; i++){
    for(int j = W; j >= w[i]; j--)
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
             // max(不放i, 放i);
}

初始化:
若要求恰好裝滿背包，那麼在初始化時除了f[0]為0外其它f[1..V]均設為-∞，這樣就可以保證最終得到的f[N]是一種恰好裝滿背包的最優解。

如果並沒有要求必須把背包裝滿，而是只希望價格盡量大，初始化時應該將f[0..V]全部設為0。因為什麼都不放也是一種放法。

## NCTU 484-Seesaw
description: 給一串數字，將數字分成兩組，使兩組總和差距最小。求最小差距為何。
solve: 想像成欲填滿總和一半重量的背包。再將總和扣掉能填滿的最大重量*2(此題價值和重量視為相等)。

#include<bits/stdc++.h>

using namespace std;

int dp[10001];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    memset(dp,0,sizeof(dp));
    int n;
    cin>>n;
    int sum=0;
    vector<int> vec(n+1);
    for(int i=1;i<=n;++i){
        int x;
        cin>>x;
        sum+=x;
        vec[i]=x;
    }
    int target=sum/2;

    for(int i=1;i<=n;++i){
        for(int j=target;j>=vec[i];j--){
            dp[j]=max(dp[j],dp[j-vec[i]]+vec[i]);
        }
    }

    cout<<sum-dp[target]*2<<endl;




return 0;
}

## ps:
另有fractional背包問題，可直接用greedy解(從最大價值的開始拿)。