# 背包問題

## info
背包問題就是一種解決，如何用有限空間取得最大價值的問題
而實際概念就是用小問題計算大問題的答案，是一種DP問題

## 01背包
[01背包題目](http://203.64.191.163/ShowProblem?problemid=a279)
物體數為N，背包容量為C，每個物品有一個Val，和一個Valume

開一個N * C的陣列，陣列的第[i][j]個就是在可以放第1~i個物品且在背包最大容量為j時的最大價值
我們每次更新f[i][j]時都有兩個選擇
1.不放第i個物品
2.清出之前的空間放入第i個物品
這兩個我們發現他都是小於目前更新的小問題
一個是f[i-1][j]，一個是f[i-1][j-Volume]
轉移式:$f[i][j]=max(f[i-1][j],f[i-1][j-Volume[i]]+Value[i])$

for(int i = 0; i < n; i++){
    for(int j = 0; j < c; j++){
        f[i][j]=max(f[i-1][j],f[i-1][j-Volume[i]]+Value[i]);
    }
}

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n, c;
    cin >> n >> c;
    vector<vector<int> > dp(n,vector<int>(c+1, 0));
    int val, v;
    cin >> val >> v;
    for(int i = 1; i < c+1 ; i++){
        if(i >= v)dp[0][i] = val;
    }
    for(int i = 1; i < n; i++){
        cin >> val >> v;
        for(int j = 1; j <= c; j++){
            if(j - v < 0) dp[i][j] = dp[i-1][j];
            else dp[i][j] = max(dp[i-1][j], dp[i-1][j-v] + val);
        }
    }
    cout << dp[n-1][c] << '\n';
}

#### 空間優化
我們會發現這樣的空間複雜度很差
所以我們可以進行一些空間優化
我們在轉移式中可以發現，我們只會用到f[i-1][任意容量]的資料
小於i-1的資料都不會再用到
所以我們可以很簡單的直接用滾動DP的方式解決這個問題
也就是開一個2*C的陣列，輪流更新0和1

不過個方法雖然簡單但實作稍微複雜了一點

取的容量也都是小於等於當前容量的
所以其實我們可以反著更新
從容量為c更新到1

#### 輸入優化
輸入我們可以發現Volume和Value的的陣列完全沒有功能
所以只要開一個變數就好
轉移式:$dp[j] = max(dp[j], d[j - Volume] + Value)$

for(int i = 1; i <= n; i++){
        int a, b;
        cin >> a >> b;
        for(int j = c; j >= b; j--){
            dp[j] = max(dp[j], dp[j - b] + a);
        }
    }

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n, c;
    cin >> n >> c;
    vector<int > dp(c+1,0);
    int val, v;
    cin >> val >> v;
    for(int i = 1; i < c+1; i++){
        if(i >= v)dp[i] = val;
    }
    for(int i = 1; i < n; i++){
        cin >> val >> v;
        for(int j = c; j >= 1; j--){
            if(j - v < 0) dp[j] = dp[j];//如果把上面的j>=1改成j>=v，這行甚至可以刪掉
            else dp[j] = max(dp[j], dp[j-v] + val);
        }
    }
    cout << dp[c] << '\n';
}

## 有限背包
[有限背包題目](http://203.64.191.163/ShowProblem?problemid=a330)
有限背包和01背包很像，只是多遍歷一層物品數量
並為了優化複雜度將物品用2的次方分堆
分堆完後可以把他們當作是新的物品，那接下來就和01背包一樣了，決定要不要拿這些分好堆的物品。
假設現在有7個東西可以放
就分成1個東西一堆(a) 2個東西一堆(b) 4個東西一堆(c)
如果你要拿1個就是拿a，2個就是拿b，3個就是拿a+b，4個就是拿c，5個就是拿b+c.....
8個就1 2 4 1
這樣原本遍歷物品個數的複雜度就會降到log
#### 二維的

#include<bits/stdc++.h>
using namespace std;
#define N 10001 //因為沒有壓空間，所以這裡不能開很大
int dp[101][N];
int main(){
    int n, c;
    cin >> n >> c;
    
    for(int i = 0; i < n; i++){
        int val, v, num;
        cin >> val >> v >> num;
        int minn = min(num, c/v);

        for(int j = 0; j <= c; j++){//不選i
            if(i > 0)dp[i][j] = dp[i-1][j];
        }

        for(int k = 1; minn > 0; k*=2){
            if(k > minn){
                k = minn;
            }
            minn-=k;
            for(int j = c; j >= v*k; j--){
                dp[i][j] = max(dp[i][j], dp[i][j-v*k] + val*k);
                //注意不是用i-1 因為上一個狀態不是i-1，而是二進位拆分的上一組
                //且因為是上一組，這裡一定要倒著dp，如果正著dp就會把上一組的蓋掉
            }
        }
    }
    cout << dp[n-1][c] << '\n';
}

#### 一維的
這題一維的反而比較簡單，因為不用多寫一個不選i的(因為只有一維，不用寫一個for把i-1轉移到i)，而且因為二進位拆分的關係，本來二維DP就也要倒著

for(int i = 0; i < n;i++){
        int val, v, num;
        cin >> val >> v >> num;
        int minn = min(num,c / v);
        for(int k = 1; minn > 0; k *= 2){
            if(k > minn)k = minn;
            minn -= k;
            for(int j = c; j >= v * k;j--){
                if(j - v * k < 0)continue;
                dp[j] = max(dp[j],dp[j - v * k] + val * k);
            }
        }
    }

#include<bits/stdc++.h>
using namespace std;
#define N 1000000
int dp[N+1];
int n,c;
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> c;
    for(int i = 0; i < n;i++){
        int val, v, num;
        cin >> val >> v >> num;
        int minn = min(num,c / v);
        for(int k = 1; minn > 0; k *= 2){
            if(k > minn)k = minn;
            minn -= k;
            for(int j = c; j >= v * k;j--){
                if(j - v * k < 0)continue;
                dp[j] = max(dp[j],dp[j - v * k] + val * k);
            }
        }
    }
    cout << dp[c] << '\n';
}

## 無限背包
[無限背包問題](http://203.64.191.163/ShowProblem?problemid=a331)
無限背包的概念也差不多
就是一個一個放放到不能放了
轉移式也差不多
但是無限背包一定要正著DP，因為可以無限拿，所以她的上一個狀態不是i-1，是上一個dp[i][j-v]，dp[j-w] 已經包含了「前面這一輪」對同一件物品的更新結果。
如果用倒著DP的方法寫，就是強迫每個i只能拿一個(因為前面的東西其實是i-1層的)

for(int i = 0; i < n; i++){
    int val, v;
    cin >> val >> v;
    for(int j = v; j <= c; j++){
        dp[j] = max(dp[j], dp[j - v] + val);
    }
}

#include<bits/stdc++.h>
using namespace std;
#define int long long

signed main(){
    int n, c;
    cin >> n >> c;
    vector<int > dp(c+1,0);
    int val, v;
    cin >> val >> v;
    for(int i = 1; i < c+1; i++){
        if(i >= v)dp[i] = val;
    }
    for(int i = 1; i < n; i++){
        cin >> val >> v;
        for(int j = v; j <= c; j++){
            dp[j] = max(dp[j], dp[j-v] + val);
        }
    }
    cout << dp[c] << '\n';
}