本文共 1629 字，大约阅读时间需要 5 分钟。
0-1背包问题是一种经典的动态规划问题，旨在在有限的重量下选择物品，使得总价值最大。该问题的核心在于每个物品只能选择一次，即要么放进背包，要么不放，而不存在放一半的情况。
0-1背包问题具有最优子结构性质，意思是说，如果我们已经解决了不含当前物品的子问题，那么再加入当前物品，就可以依据前面的结果来得出当前物品加入后的解。
假设我们有以下物品数据：
| 物品编号 | 重量W | 质值V |
|---|---|---|
| 1 | 2 | 6 |
| 2 | 2 | 3 |
| 3 | 6 | 5 |
| 4 | 5 | 4 |
| 5 | 4 | 6 |
当背包容量为10时，最大价值为15。通过分析，我们可以确定第5号物品被放入背包。
递归解法的核心思路是逐步缩小问题规模，通过物品的顺序来处理问题。这意味着我们从首个物品开始，依次向后处理每个物品，并决定是否将其放入背包。
代码示例：
#include#include using namespace std;vector > dp(n + 1, vector (c + 1, 0));for (int j = 1; j <= c; ++j) { if (j >= W[1]) { dp[1][j] = V[1]; } else { dp[1][j] = 0; }}for (int i = 2; i <= n; ++i) { for(int j = 1; j <=c;++j) { if (j < W[i]) { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]); } }}return dp[n][c];
非递归解法通常采用动态规划的方式，通过填充一个表格dp[i][j]，其中i表示物品数量，j表示重量。对于每个物品，我们决定是否在当前重量下放入该物品。
代码示例：
#include#include using namespace std;vector > dp(n + 1, vector (c + 1, 0));for (int j = 1; j <= c; ++j) { if (j >= W[1]) { dp[1][j] = V[1]; } else { dp[1][j] = 0; }}for (int i = 2; i <= n; ++i) { for (int j = 1; j <= c; ++j) { if (j < W[i]) { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]); } }}return dp[n][c];
通过对代码进行优化，我们可以得出以下结论。当背包容量为10时，最大价值为15。具体来说，我们选择了第5号物品。如果背包容量为6，最大价值为9，选择了第4号和第2号物品。
通过以上方法，我们可以有效地解决0-1背包问题。在实际应用中，通常推荐使用非递归的动态规划方法，因为其效率更高且易于理解。希望以上内容能为您提供清晰的指导。
转载地址：http://axyiz.baihongyu.com/