完全背包问题
1. 问题定义
完全背包问题是经典的动态规划问题之一。它的基本描述如下：
有一个容量为
V的背包。有
N种物品，每种物品有无限个可用。第
i种物品的重量是 w[i]，价值是 v[i]。问题：如何选择物品放入背包，使得在不超过背包容量的前提下，背包内物品的总价值最大？
关键词： 每种物品无限件。
2. 与 0-1 背包问题的区别
理解完全背包的关键是与 0-1 背包进行对比：
| 特性 | 0-1 背包 | 完全背包 |
|---|---|---|
| 物品数量 | 每件物品只有1件 | 每件物品有无限件 |
| 决策 | 对于第 i 件物品，只有两种选择：放 (1) 或不放 (0) | 对于第 i 件物品，可以选择放 0 件、1 件、2 件... 直到放不下为止 |
3. 核心思路与状态转移方程（二维数组）
1. 二维数组的状态定义
2. 初始化
3. 状态转移方程（核心区别）
【参考代码】
#include <iostream>
#include <algorithm>
using namespace std;
// 完全背包问题（二维数组版本）
// 参数：
// - weight：物品重量数组
// - value：物品价值数组
// - n：物品数量
// - W：背包最大承重
int completeKnapsack(int weight[], int value[], int n, int W) {
// dp[i][j]：前i种物品（0~i-1），背包承重为j时的最大价值
int dp[n + 1][W + 1]; // 行：物品数量（0~n），列：承重（0~W）
// 初始化：第0行（0种物品），无论承重多少，价值都为0
for (int j = 0; j <= W; j++) {
dp[0][j] = 0;
}
// 填充dp数组
for (int i = 1; i <= n; i++) { // 遍历前i种物品（i从1到n）
for (int j = 0; j <= W; j++) { // 遍历所有可能的承重（0到W）
// 情况1：不选第i-1种物品（因为数组从0开始，第i种对应下标i-1）
dp[i][j] = dp[i - 1][j];
// 情况2：选第i-1种物品（若承重足够）
if (j >= weight[i - 1]) {
// 完全背包的核心：可以重复选，因此用dp[i][j - weight[i-1]]（仍包含第i种物品）
dp[i][j] = max(dp[i][j], dp[i][j - weight[i - 1]] + value[i - 1]);
}
}
}
return dp[n][W]; // 前n种物品，承重W时的最大价值
}
int main() {
// 示例：3种物品，背包最大承重为5
int weight[] = {2, 3, 1}; // 物品重量
int value[] = {3, 5, 2}; // 物品价值
int n = 3; // 物品数量
int W = 5; // 背包最大承重
int maxVal = completeKnapsack(weight, value, n, W);
cout << "完全背包的最大价值为：" << maxVal << endl; // 输出：10
return 0;
}4. 核心思路与状态转移方程（一维数组）
1. 状态定义
2. 状态转移方程
3. 遍历顺序（关键）
【参考代码】
#include <iostream>
#include <algorithm> // 用于max函数
using namespace std;
// 完全背包问题：返回最大价值
// 参数：
// - weight：物品重量数组
// - value：物品价值数组
// - n：物品数量
// - W：背包最大承重
int completeKnapsack(int weight[], int value[], int n, int W) {
// dp[j]：承重为j的背包的最大价值（下标0~W）
int dp[1000] = {0}; // 假设背包最大承重不超过999，初始值全为0
// 遍历每种物品
for (int i = 0; i < n; i++) {
// 正向遍历承重（从物品重量到最大承重，允许重复选取）
for (int j = weight[i]; j <= W; j++) {
// 状态转移：取“不选当前物品”和“选当前物品”的最大值
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
return dp[W]; // 返回最大承重下的最大价值
}
int main() {
// 示例：3种物品，背包最大承重为5
int weight[] = {2, 3, 1}; // 物品重量数组
int value[] = {3, 5, 2}; // 物品价值数组
int n = 3; // 物品数量
int W = 5; // 背包最大承重
int maxVal = completeKnapsack(weight, value, n, W);
cout << "完全背包的最大价值为：" << maxVal << endl; // 输出：10
return 0;
}4.例子
扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
