完全背包问题
DFS_TLE
·
·
算法·理论
完全背包问题
这是蒟蒻的第一篇文章，写的不好，有错误请指出
题目
题目描述
有 n 种物品，放在容积为 m 的背包里，每种物品都有无限个。对于第 i(1 \le i \le n) 个物品有对应的体积 w_i 和价值 v_i 。请你选择一种取法，使得背包里物品的价值最大。
输入格式
第一行两个整数 n,m 表示物品的个数和背包的容积
接下来的 n 行每行两个整数 w_i 和 v_i 表示第 i 个物品的体积和价值
输出格式
一个整数，表示背包内的最大价值
输入样例
3 70
71 100
69 1
1 2
输出样例
140
暴力做法
状态描述：
#### 转移方程:
可以转化成 $01$ 背包问题。定义一个数量 $k$ 表示第 $i$ 件物品最多能装的个数。 $k$ 从 $0$ 遍历到 $\frac {j} {w_i}
dp_{i,j} = \max_{0 \le k \le \frac{j}{w_i}} \{dp_{i-1,j},dp_{i-1,j - k w_i} + k v_i \}
边界：
dp_{0,j}=0
时间复杂度
O(n \times \sum_{j=0}^m \lfloor \frac{j}{\min\{w\}} \rfloor)
代码：
#include <bits/stdc++.h>
using namespace std;
vector<int> v, w;
vector<vector<int>> dp;
int n, m;
int main()
{
cin >> n >> m;
v.resize(n + 1), w.resize(m + 1);
dp.resize(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; ++i)
cin >> w[i] >> v[i];
for (int i = 1; i <= n; ++i)
{
for (int j = 0; j <= m; ++j)
{
for (int k = 0; k <= j / w[i]; ++k)
{
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - k * w[i]] + k * v[i]);
}
}
}
cout << dp[n][m] << endl;
return 0;
}
优化：
思路：
我们注意到
dp_{i,j}=\max \{dp_{i-1,j},dp_{i-1,j-w_i}+v_i,dp_{i-1,j- 2w_i} +2v_i, \ldots, dp_{i-1,j-kw_i}+k v_i\}
dp_{i,j - w_i} + v_i = \max \left\{ dp_{i-1,j - w_i} + v_i, dp_{i-1,j - 2 w_i} + 2 v_i, dp_{i-1,j - 3 w_i} + 3 v_i, \ldots, dp_{i-1,j - (k+1) w_i} + (k+1) v_i \right\}
#### 转移方程：
$$
dp_{i,j} = \max \{ dp_{i-1,j}, dp_{i,j - w_i} + v_i \}
$$
#### 边界：
$$
dp_{0,j}=0
$$
#### 时间复杂度:
$$
O(nm)
$$
#### 代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
vector<int> v, w;
vector<vector<int>> dp;
int n, m;
int main()
{
cin >> n >> m;
v.resize(n + 1), w.resize(m + 1);
dp.resize(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; ++i)
cin >> w[i] >> v[i];
for (int i = 1; i <= n; ++i)
{
for (int j = 0; j <= m; ++j)
{
dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i]);
}
}
cout << dp[n][m] << endl;
return 0;
}
```