owned this note
owned this note
Published
Linked with GitHub
{%hackmd @ioncamp/__style %}
# 背包問題系列
https://tioj.ck.tp.edu.tw/contests/70/problems/1508
cp值背包
## 0/1背包
### 問題敘述
- 給定 $N$ 個物品，第 $i$ 個物品重量 $w_i$ ，價值 $v_i$
- 背包容量$W$
- 選擇一些物品，使得重量總和不超過容量，請問最大價值總和為何？
- $N\le 100 ，W\le 10^5$
### 解法
- 0 不選 $dp[i][j]=dp[i-1][j]$
- 1 選 $dp[i][j]=dp[i-1][j-w_i]+v_i$
- $dp[i][j]=$看前$i$個物品，在這個重量$j$之下，最大的價值可以到多少(用$w$)
- 壓縮($j--$)
:::info
- **init**
- 正確 $dp[0][0]=0$(也可以說$dp[i][0]=0,i\in \{0\ldots n\}$，只是其實之後轉移就會自然的跑到了，所以，可有可無拉XD)
- 其他 $dp[i][j]=-INF$
- **答案?**
- 正確 $ans=\max(dp[n][W],dp[n][W-1],dp[n][W-2],\ldots ,dp[n][0])$
- **這一點很容易誤解**，在大家初始狀態都是$dp[i][j]=0$的時候，$ans=\max(dp[n][W],dp[n][W-1],dp[n][W-2],\ldots ,dp[n][0])$ 和 $ans=dp[n][W]$ 是一樣的，不過在某些題目不能這樣令($dp[i][j]=0$)，所以正確的init和答案就是向上面那樣
:::spoiler code
- 一般
```cpp=
#include <bits/stdc++.h>
using namespace std;
const int maxn = 101, maxc = 100025, inf = 1e9;
int v[maxn], w[maxn];
int dp[maxn][maxc];
int main() {
int n, C;
cin >> n >> C;
for (int i = 1; i <= n; i++)
cin >> v[i] >> w[i];
dp[0][0] = 0;
for (int j = 1; j <= C; j++) dp[0][j] = -inf;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= C; j++) {
dp[i][j] = dp[i-1][j];
if (j >= w[i]) {
dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]]+v[i]);
}
}
}
int best = 0;
for (int j = 0; j <= C; j++) best = max(best, dp[n][j]);
cout << best << endl;
}
```
- 滾動陣列
```cpp=
#include <bits/stdc++.h>
using namespace std;
const int maxn = 101, maxc = 100025, inf = 1e9;
int v[maxn], w[maxn];
int dp[maxn];
int main() {
int n, C;
cin >> n >> C;
for (int i = 1; i <= n; i++)
cin >> v[i] >> w[i];
dp[0] = 0;
for (int j = 1; j <= C; j++) dp[j] = -inf;
for (int i = 1; i <= n; i++) {
for (int j = C; j >= w[i]; j--) {
dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
}
}
int best = 0;
for (int j = 0; j <= C; j++) best = max(best, dp[j]);
cout << best << endl;
}
```
:::
- [練習1](https://atcoder.jp/contests/dp/tasks/dp_d)
- [練習2](https://judge.tcirc.tw/ShowProblem?problemid=d075)
- [解答](https://github.com/yozen0405/c-projects/blob/main/judge.tcirc.tw/d075.cpp)
- [練習3](https://tioj.ck.tp.edu.tw/problems/2222)
- [解答](https://github.com/yozen0405/c-projects/blob/main/tioj/2222.cpp)
- [應用1](https://codeforces.com/problemset/problem/1633/D)
- [應用2](https://atcoder.jp/contests/dp/tasks/dp_x)
- [解答](https://github.com/yozen0405/c-projects/blob/main/AtCoder/X%20-%20Tower.cpp)
- [類似技巧(進階)](https://zerojudge.tw/ShowProblem?problemid=e900)
- [解答](https://github.com/yozen0405/c-projects/blob/main/zerojudge/e900.cpp)
- [變化](https://tioj.ck.tp.edu.tw/problems/1508)
## 算方法數
- https://cses.fi/problemset/task/1093
- 答案算出來不能直接/2要去乘2模1e9+7的模逆元
- [證明:為什麼除以一個數取模等於乘以這個數的模逆元
](https://cdn.discordapp.com/attachments/972879937180692551/990259615117754468/20220625_221558.jpg)
```cpp=
int f(int W,vector<int>& v,vector<int>& w){
int n=v.size();
vector<int> cnt(W+1);
vector<int> dp(W+1,-INF);
dp[0]=0;
cnt[0]=1;
for(int i=1;i<=n;i++){
for(int j=W;j>=w[i];j--){
if(dp[j]==dp[j-w[i]]+v[i]){
cnt[j]+=cnt[j-w[i]];
cnt[j]%=M;
}
else if(dp[j-w[i]]+v[i]>dp[j]){
dp[j]=dp[j-w[i]]+v[i];
cnt[j]=cnt[j-w[i]];
cnt[j]%=M;
}
}
}
return cnt[W];
}
```
## 變化1
- $W$超大$v$很小
### 問題敘述
- 給定 $N$ 個物品，第 $i$ 個物品重量 $w_i$ ，價值 $v_i$
- 背包容量$W$
- 選擇一些物品，使得重量總和不超過容量，請問最大價值總和為何？
- $N\le 100 ，W\le 10^9，\sum v_i \le 10^5$
### 解法
- $dp[i][j]=$看前$i$個物品，在這個價值$j$之下，最少的重量可以到多少(用$v$)
```cpp=
memset(dp,INF,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n;i++){
for(int j=1e5;j>=v[i];j--){
dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
}
}
int ans=-1;
for(int j=1e5;j>=1;j--) if(dp[j]<=W) ans=max(ans,j);
```
https://atcoder.jp/contests/dp/tasks/dp_e
## 變化2
- $N=4 \texttt{ but }W,v \approx10^9$
### 問題敘述
- 給定 $N$ 個物品，第 $i$ 個物品重量 $w_i$ ，價值 $v_i$
- 背包容量$W$
- 選擇一些物品，使得重量總和不超過容量，請問最大價值總和為何？
- $N\le 40 ，W\le 10^9，\sum v_i\le 10^9$
### 解法
- 集合
- 折半枚舉
:::spoiler code
```cpp=
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
using pii = pair<int, int>; // (重量, 價值)
// A 的長度是 2^|a|，存放 a 所有子集合總和
vector<pii> allSubsetSum(vector<pii> a) {
int n = a.size();
vector<pii> A = {{0, 0}};
for (int i = 0; i < n; i++) {
for (int j = A.size() - 1; j >= 0; j--) {
A.push_back({A[j].first + a[i].first, A[j].second + a[i].second});
}
}
sort(A.begin(), A.end());
for (int i = 1; i < A.size(); i++) {
A[i].second = max(A[i].second, A[i - 1].second);
//他如果放得下那也一定有辦法改成能比他重量小的價值
}
return A;
}
int main() {
cin.tie(0);
cin.sync_with_stdio(0);
int n, W;
vector<pii> a, b;
cin >> n >> W;
for (int i = 0; i < n; i++) {
int w, v;
cin >> w >> v;
if (i < n / 2) {
a.push_back({w, v});
} else {
b.push_back({w, v});
}
}
int ans = 0; // w 總和小於等於 W 的最大 v 總和
vector<pii> A = allSubsetSum(a);
vector<pii> B = allSubsetSum(b);
for (pii x : B) {
auto it = upper_bound(A.begin(), A.end(), pii{W - x.first, INT_MAX});
if (it != A.begin()) {
it = prev(it);
ans = max(ans, x.second + it->second);
}
}
cout << ans << '\n';
return 0;
}
/*
input:
5 10
1 19
2 22
3 18
7 3
10 100
output:
100
*/
```
- $O(2\times 2^N)$
:::
## 變化3
### 題目敘述
- 找第 $k$ 大的價值
:::spoiler code
```cpp=
#include <bits/stdc++.h>
using namespace std;
vector<long long>d;
long long bit[1<<21];
vector<pair<long long, long long>>gen_subset(vector<pair<int,int>>v) {
vector<pair<long long, long long>>ret;
for (int i = 0 ; i < (1<<v.size()) ; i++) {
long long sum_w = 0, sum_v = 0;
for (int j = 0 ; j < v.size() ; j++) {
if (i & (1<<j)) {
sum_w += v[j].first;
sum_v += v[j].second;
}
}
ret.push_back({sum_w, sum_v});
}
return ret;
}
int bit_query(int x) {
int ret = 0;
while (x) {
ret += bit[x];
x -= x & (-x);
}
return ret;
}
void bit_update(int x) {
while (x <= d.size()) {
bit[x]++;
x += x & (-x);
}
}
int main() {
int n;
long long k, lim;
cin >> n >> k >> lim;
vector<pair<int,int>>p1, p2;
for (int i = 0 ; i < n / 2 ; i++) {
long long a, b;
cin >> a >> b; // weight, value
p1.push_back({a, b});
}
for (int i = n / 2 ; i < n ; i++) {
long long a, b;
cin >> a >> b;
p2.push_back({a, b});
}
vector<pair<long long, long long>>v1, v2;
v1 = gen_subset(p1);
v2 = gen_subset(p2);
sort(v1.begin(), v1.end());//小到大
sort(v2.rbegin(), v2.rend());//大到小
//1.大到小才能維護mid-i.second從小到大
//2.雙指針
//才能使ptr在動的時候再i:v2的i更新的時候(i變小)我的ptr才能保證
//只能不動或向右動，讓時間複雜度變O(n)
for (auto &i : v1) {
d.push_back(i.second);
}
sort(d.begin(), d.end());
d.erase(unique(d.begin(), d.end()),d.end());
//離散化
//1.sort
//2.unique
//缺一不可
//unique 回傳把陣列的重複拉到陣列的最後，並回傳unique之後的後一個位置
//credit: https://www.cnblogs.com/heyonggang/p/3243477.html
long long l = 0, r = 1e12; //二分搜價值
while (r - l > 1) {
long long mid = (l + r) / 2;
int ptr = 0;
long long cnt = 0;
memset(bit, 0, sizeof(bit));
for (auto &i : v2) {
while (ptr < v1.size() && v1[ptr].first + i.first <= lim) {
int idx = lower_bound(d.begin(), d.end(), v1[ptr].second) - d.begin() + 1;
bit_update(idx);
ptr++;
}
int idx = lower_bound(d.begin(), d.end(), mid - i.second) - d.begin() + 1;
cnt += ptr - bit_query(idx-1); //why? idx-1 -> >= x的方法數有等於
//把全部(ptr)扣掉 小於的
//value比(mid - i.second)(全部-v2=v1因為只儲存v1的東西)
//cout << ptr <<' '<<idx <<' '<<cnt << endl;
}
if (cnt < k) { // 價值 >= x 的方法數
r = mid;
}
else {
l = mid;
}
}
cout << l << endl;
}
/*
problem:
找第k大的價值
Input
4 3 3
1 2
1 3
1 7
1 12
Output
19
*/
```
:::
## 變化4
- 包包容量 $2^W$ 物品重量 $2^{a}$
- greedy
- 想法 $2^{n-1}+2^{n-1} \le 2^n$
- 把大的倆倆合併
- https://zerojudge.tw/ShowProblem?problemid=c835
```cpp=
cin >> n >> m;
for(int i = 0; i < n; ++i) {
int a, b;
cin >> a >> b;
if(a <= m)
pq[a].push(b);
}
for(int i = 0; i < m; ++i) {
while(!pq[i].empty()) {
if(pq[i].size() == 1) {
pq[i + 1].push(pq[i].top());
break;
}
ll a = pq[i].top();
pq[i].pop();
ll b = pq[i].top();
pq[i].pop();
pq[i + 1].push(a + b);
}
}
cout << pq[m].top() << "\n";
```
## 最小字典序
- 跟LIS一樣**反著做**
```cpp=
// dp[i][j]:= i~n 的物品湊出重量為 j 的ans
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1e3 + 5;
int dp[maxn][maxn];
int w[maxn], v[maxn];
int n,W;
signed main() {
cin >> n >> W;
for(int i = 1; i <= n ;i++){
cin >> w[i] >> v[i];
}
memset(dp, -INF, sizeof dp);
dp[n + 1][0] = 0;
int wei, mx = 0;
// 反向操作
for(int i = n; i > 0; i--){
for(int j = 0; j <= W; j++){
if(w[i] > j) {
dp[i][j] = dp[i+1][j];
}
else {
dp[i][j] = max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]);
}
if (mx < dp[i][j]) {
mx = dp[i][j];
wei = j;
}
}
}
cout << dp[1][wei] << "\n";
for (int i = 1; i <= n; ++i) {
// 字典序題目特色
if (wei >= w[i] && dp[i][wei] == dp[i + 1][wei - w[i]] + v[i]) {
cout << i << ' ';
wei -= w[i];
}
}
}
```
## 無限背包
- 又稱完全背包
### 解法
- 0 不選 $dp[i][j]=dp[i-1][j]$
- 1 選 $dp[i][j]=dp[i][j-w_i]+v_i$
- 壓縮($j++$)
- $ans=\max(dp[n][W],dp[n][W-1],dp[n][W-2],\ldots ,dp[n][0])$
```cpp=
for(int i=1;i<=n;i++){
for(int j=0;j<=w[i];j++){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
```
## 有限背包
- 又稱多重背包
### 解法
- 把物品拆成 $\log_2k$
- 例如100=1+2+4+8+16+32+37
- 每個都是為單獨的物品做0/1背包
```cpp=
for (int k = 1; k <= s; k <<= 1) {
v[++cnt] = k * a;
w[cnt] = k * b;
s -= k;
}
if (s) {
v[++cnt] = s * a;
w[cnt] = s * b;
}
```
### 優化
- $dp(i,j)=\max\{dp(i-1,j-x\times w_i)+\text{cost}\}$
- 單調隊列
```cpp=
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
//多重背包问题： 限制每种物品可取次数
//究极优化：单调队列
const int M = 20010, N = 1010;
int n, m;
int dp[M], g[M];
int Q[M]; //队列只存储在同余的集合中是第几个，不存储对应值
int main() {
cin >> n >> m;
for(int i = 0; i < n; i ++){
int w, v, s;
cin >> w >> v >> s; // weight, value, number
//复制一份副本g，因为这里会是从小到大，不能像0-1背包那样从大到小，所以必须申请副本存i-1状态的，不然会被影响
memcpy(g, dp, sizeof dp);
for(int r = 0; r < w; r ++) { //因为只有与v同余的状态 相互之间才会影响，余0,1,...,v-1 分为v组
int head = 0, tail = -1;
for(int k = 0; r + k * w <= m; k ++) { //每一组都进行处理，就相当于对所有状态都处理了
//队头不在窗口里面就踢出（队头距离要更新的dp超过了最大个数s，尽管它再大也要舍去，因为达不到）
if(head <= tail && k - Q[head] > s) head++;
//这第k个准备进来，把不大于它的队尾统统踢掉，也是为了保持队列的单调降（判断式实际上是两边同时减去了k * w）
//实际意义应该是 g[r + k * v] >= g[r + que[tail] * v] + (k - que[tail]) * w 为判断条件
while (head <= tail && g[r + k * w] >= g[r + Q[tail] * w] + (k - Q[tail]) * v) tail --;
Q[++ tail] = k; //将第k个入列，队列只存储在同余中是第几个，不存储对应值
//余r的这组的第k个取队头更新，队头永远是使之max的决策
dp[r + k * w] = g[r + Q[head] * w] + (k - Q[head]) * v;
}
}
}
cout << dp[m] << endl;
return 0;
}
```
- https://cses.fi/problemset/task/1159
## 混和背包
- 最多取一次
- 最多取 $k$ 次
- 可以取無限次
### 解法
- 無限多次其實也不是無限，最多也就$\displaystyle \frac{W}{w_i}$次
- 想成有限背包
## 二維背包
### 問題敘述
- 給定 $N$ 個物品，第 $i$ 個物品要消耗兩種代價 $a_i,b_i$ ，價值 $v_i$
- 背包容量的兩種代價$W,U$
- 選擇一些物品，使得重量總和不超過容量，請問最大價值總和為何？
- $N\le 100 ，W,U\le 10^3$
### 解法
- $dp[i][j][k]$ 看前$i$項物品,第一種代價是$j$,第二種代價是$k$
- 0不選 $dp[i][j][k]=dp[i-1][j][k]$
- 1選 $dp[i][j][k]=dp[i][j-a_i][k-b_i]+v_i$
- $O(NWU)$
## 限量背包
### 問題敘述
- 給定 $N$ 個物品，第 $i$ 個物品重量 $w_i$ ，價值 $v_i$
- 背包容量$W$
- 選擇一些物品，最多選 $M$ 個，使得重量總和不超過容量，請問最大價值總和為何？
- $N,M\le 100 ，W\le 10^5$
### 解法
- 當二維背包
- 把選這個物品的代價是1，總代價是M
## 分組背包
### 問題敘述
- 給定 $N$ 個物品，第 $i$ 個物品重量 $w_i$ ，價值 $v_i$ ，組別是 $k_i$
- 背包容量$W$
- 選擇一些物品，每組最多選 $1$ 個，共有 $K$ 組，使得重量總和不超過容量，請問最大價值總和為何？
- $N,K\le 100 ，W\le 10^5$
### 解法
- $dp[i][j]=$ 前 $i$ 組重量是 $j$ 可以選到的最大價值總和
- 如果選到組 $k_i$ 裡面的 $u$ 物品
- 0不選 $dp[i][j]=dp[i-1][j]$
- 1選 $dp[i][j]=dp[i-1][j-w_u]+v_u$
```cpp=
//v[i][u] 組別i裡面的第u個的價值
//w[i][u] 組別i裡面的第u個的價值
for(int i=1;i<=K;i++){
for(int j=W;j>=0;j--){
for(int u=1;u<=v[i].size();u++){
if(j-v[i][u]>=0) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[u]]+v[u]);
}
}
}
```
- $O(NW)$ 因為$K$組每組$x$個，$\sum_{i=1}^k x_i=N$
## 分數背包
### 問題敘述
- 給定 $N$ 個物品，第 $i$ 個物品重量 $w_i$ ，價值 $v_i$
- 背包容量$W$
- **物品可以分割**
- 選擇一些物品，使得重量總和不超過容量，請問最大價值總和為何？
### 解法
- 貪心
- 依照 CP 值排序由高到低取
- https://tioj.ck.tp.edu.tw/problems/2223
## bitset
- 答案 true false 的可以思考看看能不能用位元運算
- 性質: 背包, 總和
- 取交集 -> bitset
### 0/1 背包
- 特性: 重量，價值一樣，問可以可以達到某個重量
- $\texttt{dp |= (dp << w[i])}$
- [TIOJ 1993](https://tioj.ck.tp.edu.tw/problems/1993)
### 有限背包
- 物品 i 有 c[i] 個
- 把 c[i] 分成 log c[i] 組,用 0/1 背包做
### 無限背包
- c[i] = m / w[i] 當有限背包解
###### tags: `algo`
Google Drive
Gist
Clipboard
Sign in with Wallet
