完全背包问题 — 思路分析
相比与前面的01背包问题,其多了个条件即每个物品之间所能选用的次数是无限的,只要不超过背包的容量
同样借助我们之前的 闫氏dp分析的模型
| 集合 : 从1 ~ i 种物品中选,且总体积不超过j的集合
|
|
|----------状态表示--------|
| |
| |
| |属性 : 集合中所有可行方案中价值的最大值
DP
|
|
|
|
|------------状态计算 : 根据集合划分,将一个大集合划分为若干个子集,
设我们要求解f(i,j), 然后来尝试将其分为更小的集合
对集合f(i,j) , 这个集合我们可以把它先分为两部分, 一部分是 (1) 不包含第 i 种硬币的可行方案数,(2) 必包含第 i 种硬币的可行方案
|----------------(1) 不包含第 i 种物品的可行方案数中的价值最大的为 f(i - 1, j);
|
|
f(i,j)
|
|----------------(2) 必包含第 i 种物品的可行方案 : 这里又分为第i个物品有1,2 ,3 ... , k(k最大 j / v[i] 下取整)个的方案 v[i]为第i个物品的体积)
对于(2)这个子集中又分为多个集合, 即i个物品有1,2 ,3 … , k(k最大 j / v[i] 下取整)个的子集问题,
f(i - 1, j -v[i]) + w[i] , f(i - 2, j - 2v[i]) + 2w[i], f(i - 3, j - 3v[i] + 3w[i]) , ...., f(i - 1, j - kv[i]) + k * w[i] (k = j/ v[i] 下取整)
要从上面的 1 ~ k 个 集合中选出一个价值最大的数作为 f(i, j) 第(2)子集中的值.
故这里可以推导出一个朴素做法 3 层 for循环 , 最后一层的for依次遍历 第 i 个硬币是0, 1 , 2, 3 ,… k的情况, 但这样时间复杂度太大,会TLE
#include<iostream>
using namespace std;
constexpr int N = 1010;
int n,m;
int v[N], w[N];
int f[N][N];
auto main() -> int
{
cin >> n >> m;
for(int i = 1; i <= n; ++i) cin >> v[i] >>w[i];
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
for(int k = 0; k * v[i] <= j; ++k)
f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
cout << f[n][m] << endl;
return 0;
}
故这种方法不可行,观察式子发现 f(i, j - v[i]) 所表示的子集为:
|----------------(1) 不包含第 i 种物品的可行方案数中的价值最大的为 f(i - 1, j - v[i]);
|
|
f(i,j - v[i])
|
|----------------(2) 必包含第 i 种物品的可行方案 : f(i - 1, j - 2v[i]) + w[i] , f(i - 1, j - 3v[i]) + 2 * w[i] , .... , f(i - 1, j - kv[i]) + (k - 1) * w[i] (k = j/ v[i] 下取整) 中取一个最大
注意这里f(i,j - v[i])中的每一项, 与f(i,j)相比,均少w[i], 故f(i, j) 的 (2) 部分可以表示为 f(i, j - v[i]) + w[i]
故写出如下代码
#include<iostream>
using namespace std;
constexpr int N = 1010;
int n , m;
int v[N], w[N];
int f[N][N];
auto main() -> int
{
cin >> n >> m;
for(int i = 1; i <= n; ++i) cin >> v[i] >> w[i];
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
f[i][j] = f[i - 1][j];
if(j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
}
}
cout << f[n][m] << endl;
return 0;
}
空间优化
#include<iostream>
using namespace std;
constexpr int N = 1010;
int n , m;
int v[N], w[N];
int f[N];
auto main() -> int
{
cin >> n >> m;
for(int i = 1; i <= n; ++i) cin >> v[i] >> w[i];
for(int i = 1; i <= n; ++i)
for(int j = v[i]; j <= m; ++j)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m] << endl;
return 0;
}