完全背包问题
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; }