# 多重背包模型

## 例题

### 数据范围

$0 \lt N, V \le 100$
$0 \lt v_i, w_i, s_i \le 100$

4 5
1 2 3
2 4 1
3 4 3
4 5 2

10

## 分析 & 代码

### 暴力解法

• 时间复杂度：$O(N\cdot V^2)$ (最坏情况)
• 空间复杂度：$O(V)$
#include <iostream>
#include <algorithm>

using namespace std;

const int SIZE = 1010;
int N, V;
int v[SIZE], w[SIZE], s[SIZE];
int dp[SIZE];

int main()
{
cin >> N >> V;
for (int i = 1; i <= N; i++)
cin >> v[i] >> w[i] >> s[i];
for (int i = 1; i <= N; i++)
for (int j = V; j >= v[i]; j--)
for (int k = 0; k * v[i] <= j && k <= s[i]; k++)
dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]);
cout << dp[V] << endl;
return 0;
}

### 二进制优化

• 时间复杂度：$O(N\cdot\log{S}\cdot V)$
• 空间复杂度：$O(V)$ (已包含空间优化)
#include <iostream>
#include <algorithm>

using namespace std;

// 需要注意各个数组的大小
const int SIZE_NlogS = 25000, SIZE_V = 2010;
int N, V, idx;
int v[SIZE_NlogS], w[SIZE_NlogS];
int dp[SIZE_V];

int main()
{
cin >> N >> V;
// 物品读入
for (int i = 1; i <= N; i++)
{
int a, b, s;
cin >> a >> b >> s;
int k = 1;
// 物品打包
while (k <= s)
{
v[++idx] = a * k;
w[idx] = b * k;
s -= k;
k *= 2;
}
if (s)
{
v[++idx] = a * s;
w[idx] = b * s;
}
}
// 01-背包问题
for (int i = 1; i <= idx; i++)
for (int j = V; j >= v[i]; j--)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
cout << dp[V] << endl;
return 0;
}

### 单调队列优化

\begin{align} dp(i,j)&=\max\left\{dp(i-1,j),dp(i-1,j-v_i)+w_i,\cdots,dp(i-1,j-kv_i)+k w_i\right\}\\ dp(i,j-v_i)&=\max\left\{dp(i-1,j-v_i),\cdots,dp(i-1,j-kv_i)+(k-1)w_i\right\}\\ &\Rightarrow dp(i,j)=\max\left\{dp(i-1,j),dp(i,j-v_i)+w_i\right\} \end{align}

\begin{align} dp(i,j)&=\max\left\{dp(i-1,j),dp(i-1,j-v_i)+w_i,\cdots,dp(i-1,j-s_iv_i)+s_iw_i\right\}\\ dp(i,j-v_i)&=\max\left\{dp(i-1,j-v_i),\cdots,dp(i-1,j-(s_i+1)v_i)+s_iw_i\right\}\\ \end{align}

$$\dots\dots,\;\;dp(i,r+3v)-3w,\;\;dp(i,r+2v)-2w,\;\;dp(i,r+v)-w,\;\;dp(i,r)$$

• 时间复杂度：$O(N\cdot V)$
• 空间复杂度：$O(V)$ (已包含空间优化)
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

int main()
{
int N, V;
cin >> N >> V;
vector<int> v(N + 10), w(N + 10), s(N + 10);
for (int i = 1; i <= N; i++)
cin >> v[i] >> w[i] >> s[i];
vector<int> dp(V + 10), lst(V + 10), que(V + 10);
for (int i = 1; i <= N; i++)
{
lst = dp;
for (int r = 0; r < v[i]; r++)
{
int hh = 0, tt = -1;
for (int k = r; k <= V; k += v[i])
{
if (hh <= tt && que[hh] < k - s[i] * v[i])
++hh;
while (hh <= tt && lst[que[tt]] - (que[tt] - r) / v[i] * w[i] <= lst[k] - (k - r) / v[i] * w[i])
--tt;
if (hh <= tt)
dp[k] = max(dp[k], lst[que[hh]] - (que[hh] - k) / v[i] * w[i]);
que[++tt] = k;
}
}
}
cout << dp[V] << endl;
return 0;
}

# 分组背包问题

## 例题

### 输入格式

• 每组数据第一行有一个整数 $S_i$，表示第 $i$ 个物品组的物品数量；
• 每组数据接下来有 $S_i$ 行，每行有两个整数 $v_{ij}, w_{ij}$，用空格隔开，分别表示第 $i$ 个物品组的第 $j$ 个物品的体积和价值；

### 数据范围

$0 \lt N, V \le 100$
$0 \lt S_i \le 100$
$0 \lt v_{ij}, w_{ij} \le 100$

3 5
2
1 2
2 4
1
3 4
1
4 5

8

## 分析

• 时间复杂度：$O(V\cdot\sum{S})$
• 空间复杂度：$O(V)$ (已包含空间优化)
#include <bits/stdc++.h>

using namespace std;

const int SIZE = 110;
int N, V;
int v[SIZE][SIZE], w[SIZE][SIZE], S[SIZE];
int dp[SIZE];

int main()
{
cin >> N >> V;
for (int i = 1; i <= N; i++)
{
cin >> S[i];
for (int j = 0; j < S[i]; j++)
cin >> v[i][j] >> w[i][j];
}
for (int i = 0; i <= N; i++)
for (int j = V; j >= 0; j--)
for (int k = 0; k < S[i]; k++)
if (v[i][k] <= j)
dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]);
cout << dp[V] << endl;
return 0;
}

# 混合背包问题

## 例题

• 第一类物品只能用 $1$ 次（01背包）；
• 第二类物品可以用无限次（完全背包）；
• 第三类物品最多只能用 $s_i$ 次（多重背包）；

### 输入格式

• $s_i=−1$ 表示第 $i$ 种物品只能用 $1$ 次；
• $s_i=0$ 表示第 $i$ 种物品可以用无限次；
• $s_i>0$ 表示第 $i$ 种物品可以使用 $s_i$ 次；

### 数据范围

$0<N,V≤1000$
$0<vi,wi≤1000$
$−1≤s_i≤1000$

4 5
1 2 -1
2 4 1
3 4 0
4 5 2

8

## 分析

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

void solve()
{
int N, V;
cin >> N >> V;
vector<int> dp(V + 10);
for (int i = 1; i <= N; i++)
{
int v, w, s;
cin >> v >> w >> s;
if (s == 0) // 完全背包
{
for (int j = v; j <= V; j++)
dp[j] = max(dp[j], dp[j - v] + w);
}
else // 0-1背包 和 多重背包
{
s = abs(s); // 一律当多重背包转化成0-1背包
vector<int> vv, ww;
int k = 1;
while (k <= s)
{
vv.push_back(v * k);
ww.push_back(w * k);
s -= k;
k *= 2;
}
if (s)
{
vv.push_back(v * s);
ww.push_back(w * s);
}
for (int j = 0; j < vv.size(); j++)
for (int k = V; k >= vv[j]; k--)
dp[k] = max(dp[k], dp[k - vv[j]] + ww[j]);
}
}
cout << dp[V] << endl;
}

signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}