0-1 背包问题 C++ 代码详解 - HLOJ 1006 - 常规

0-1 背包问题 C++ 代码详解 - HLOJ 1006

问题描述: 给定 n 种物品（每种仅一个）和一个容量为 c 的背包，要求选择物品装入背包，使得装入背包中物品的总价值最大。

输入格式: 测试数据有多组，处理到文件尾。每组测试数据输入 3 行，第 1 行为两个整数 n（1≤n≤400）和 c (1≤c≤1500)，分别表示物品数量与背包容量，第二行为 n 个物品的重量 w'i'（1≤i≤n），第三行为这 n 个物品的价值 v'i'（1≤i≤n）。物品重量、价值都为整数。

输出格式: 对于每组测试，在一行上输出一个整数，表示装入背包的最大总价值（结果保证在 2'31' -1 范围内）。

输入样例:

4 9
2 3 4 5
3 4 5 7
25 100
42 6 48 13 38 124 8 17 41 25 41 26 47 41 171 25 7 30 35 7 17 32 45 27 38
49 19 53 40 22 4 36 20 49 25 61 48 67 34 57 52 46 45 33 41 20 38 34 58 63

输出样例:

12
292

代码长度限制: 16 KB

时间限制: 400 ms

内存限制: 64 MB

C++ 代码:

#include <iostream>
using namespace std;

int main() {
    int n, c;
    while (cin >> n >> c) {
        int w[401], v[401];
        int dp[1501] = {0}; // dp[i] 表示容量为 i 的背包所能装的最大价值
        for (int i = 1; i <= n; i++) {
            cin >> w[i];
        }
        for (int i = 1; i <= n; i++) {
            cin >> v[i];
        }
        for (int i = 1; i <= n; i++) {
            for (int j = c; j >= w[i]; j--) {
                dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
            }
        }
        cout << dp[c] << endl;
    }
    return 0;
}

代码解析:

定义数组:
- w[401]：存储物品的重量，下标从 1 开始，方便后续循环访问。
- v[401]：存储物品的价值，下标从 1 开始，方便后续循环访问。
- dp[1501]：存储动态规划的结果，dp[i] 表示容量为 i 的背包所能装的最大价值。
输入数据:
- 使用 cin 输入物品数量 n，背包容量 c，以及每个物品的重量 w[i] 和价值 v[i]。
动态规划:
- 循环遍历每个物品 i，从容量 c 开始逆序循环遍历背包容量 j，判断当前物品是否能放入背包。
- 如果可以放入，则比较 dp[j]（不放入当前物品的最大价值）和 dp[j - w[i]] + v[i]（放入当前物品的最大价值），选择更大的值更新 dp[j]。
输出结果:
- 输出 dp[c]，即容量为 c 的背包所能装的最大价值。

总结:

该代码使用了动态规划的思想来解决 0-1 背包问题，思路清晰，代码简洁，易于理解和实现。

优化建议:

可以使用空间优化，将二维数组 dp 优化为一维数组，减少内存占用。
可以根据题目要求，调整数组大小和循环范围，提高代码效率。

更多学习资源:

希望以上内容能够帮助您更好地理解和解决 0-1 背包问题！