完全背包问题
ChatGPT给出的思路
- 咱就把0-1背包问题讲个通透! - 知乎 - 知乎专栏
- 咱就把完全背包问题学个通透! - 知乎 - 知乎专栏
- 背包问题总结( 1 ) 01 背包,完全背包,多重背包,分组背包 - 知乎
- 计算机科学中的「背包问题(Knapsack problem)」是什么,它有什么应用场景? - 知乎
- 01背包和完全背包(可能是最易懂最详细的) - Csdn博客
解决完全背包问题的关键在于理解每种物品可以无限使用的条件如何影响动态规划的设计。这里给你的是一个详细的思路说明,而不是具体代码。
首先,完全背包问题的基本形式是有一个背包和N种物品,背包的最大容量为W。每种物品有各自的重量和价值,你的目标是选择一些物品放入背包,使得背包内物品的总价值最大,同时不超过背包的最大容量。与01背包问题不同的是,每种物品你可以选择无限次。
动态规划的设计思路如下:
-
定义状态: 设
dp[i][j]
表示从前i
种物品中选择,总重量不超过j
时的最大价值。这里i
可以理解为决策阶段,而j
是决策时考虑的背包容量。 -
状态转移方程: 对于每一种物品
i
,你都可以选择放入或不放入背包,但由于物品数量无限,你可以选择放入任意多次,只要总重量不超过背包容量。因此,状态转移方程可以表示为:
$$ dp[i][j] = \max(dp[i-1][j], dp[i][j-weight[i]] + value[i]) $$
这里dp[i-1][j]
代表不选择当前物品时的最大价值,dp[i][j-weight[i]] + value[i]
代表选择当前物品至少一次时的最大价值。需要注意的是,由于物品可以无限选取,我们在考虑dp[i][...]
时仍然保留i
维度,而不是转移到i-1
。 -
初始化:
dp[0][...] = 0
,即当没有物品可以选择时,任何容量的背包其价值都是0。对于dp[...][0]
,也应该初始化为0,因为容量为0的背包不能装入任何物品。 -
计算顺序: 从小到大计算所有
dp[i][j]
的值。这里的计算顺序对于完全背包问题来说比较灵活,因为每个物品可以无限选取,所以可以在更新dp[i][j]
时,先遍历物品,再遍历容量。 -
结果:
dp[N][W]
即为最终结果,表示选择前N种物品,背包容量为W时的最大价值。
总结来说,完全背包问题的关键在于理解物品无限可选的性质如何影响状态转移方程的设计。通过合理定义状态和状态转移方程,使用动态规划可以有效解决这一问题。
根据思路写出的代码
#include <stdio.h>
#include <stdlib.h>
int N, V;
int w[1010];
int v[1010];
int dp[1010][1010];
int max(int a, int b)
{
return (a > b) ? a : b;
}
int main()
{
scanf("%d %d", &N, &V);
for (int i = 1; i <= N; i++)
{
scanf("%d %d", &(w[i]), &(v[i]));
}
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= V; j++)
{
if (j < w[i])
{
dp[i][j] = dp[i - 1][j];
}
else
{
dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i]);
}
}
}
if (0) // 调试输出
{
for (int i = 0; i <= N; i++)
{
for (int j = 0; j <= V; j++)
{
printf("%d ", dp[i][j]);
}
printf("\n");
}
}
printf("%d\n", dp[N][V]);
return 0;
}