---
tags: algorithm
---
# DP

## 背包問題

來看到`DP`的一個經典例題，背包問題。
#### 問題簡述
給予一個容量為`k`的背包。
和一些物品，每個物品都有其大小和價值。
問再不超過背包容量的條件下，能裝入的最大價值。

### 0/1背包
每項物品都只有一個

背包容量為`M`,有`N`個物品。
$v[i] \implies 第i個物品的價值$
$w[i] \implies 第i個物品的重量$

#### DP解

vector<int> v(N), w(N);
vector<vector<int>> dp(N, vector<int>(M + 1, 0));

for(int i = 0; i <　N; i++) {
    for(int j = 0; j < w[i]; j++) 
        dp[i][j] = dp[i - 1][j];
    for(int j = w[i]; j <= M; j++)
        dp[i][j] = max(dp[i - 1][j], v[i] + dp[i - 1][j - w[i]]);
}

#### 滾動DP

vector<int> v(N), w(N);
vector<int> dp(M + 1, 0);

for(int i = 0; i < N ;i++) {
    for(int j = M; j >= w[i]; j--)
        dp[j] = max(dp[j], v[i] + dp[j - w[i]]);
}

:::info
Q: 為什麼要從後往前DP呢?
:::

### 無限背包

從前往後`DP`, 即可。

vector<int> v(N), w(N);
vector<int> dp(M + 1, 0);

for(int i = 0; i < N ;i++) {
    for(int j = w[i]; j <= M; j++)
        dp[j] = max(dp[j], v[i] + dp[j - w[i]]);
}

---

### 有限背包
`DP，位元運算`

#### 一開始的想法
把每一個物品都做一次`O/1背包`。

vector<int> v(N), w(N), num(N);
for(int i = 0; i < N;i ++) 
    for(int t = 0; t < num[i]; t++) 
        for(int j = M; j >= w[i]; j--) 
            dp[j] = max(dp[j], v[i] +　dp[j - w[i]])；

#### 優化
把物品的數量拆成二的倍數。

vector<int> v(N), w(N), num(N);
for(int i = 0; i < N; i++) {
    int rest = num[i];
    int weight, val;
    
    for(int t = 0; t <= rest; t <<= 1) { //t *= 2
        rest -= t;        
        weight = t * w[i], val = t * val[i];
        
        for(int j = M;j >= weight; j--)
            dp[j] = max(dp[j], val + dp[j - weight]);
    }
    
    
    weight = t * w[i], val = t * v[i];
    
    for(int j = M; j >=; j++) {
        dp[j] = max(dp[j], val + dp[j - weight]);
    }
}