0-1背包问题题解 题目分析

本题是经典的 0-1背包问题，每个物品只能选择一次，目标是使背包内物品的总价值最大。

解题思路 状态定义

定义 dp[i][j]表示：考虑前 i个物品，在背包容量为 j的情况下，能获得的最大价值。

状态转移方程

对于第 i个物品，有两种选择：

不放入背包：dp[i][j] = dp[i-1][j]

放入背包（前提：j ≥ w[i]）：dp[i][j] = dp[i-1][j-w[i]] + p[i]

综合两种情况：

复制 dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + p[i]) (j ≥ w[i]) dp[i][j] = dp[i-1][j] (j < w[i]) 边界条件

dp[0][j] = 0：没有物品时，任何容量的价值都是0

dp[i][0] = 0：容量为0时，无法放入任何物品

代码实现 cpp 下载 复制 #include<bits/stdc++.h> #define int long long const int N=2e6+10; using namespace std; int maxw,n,w[N],p[N],dp[105][20005];

signed main(){ // 输入背包容量和物品数量 cin>>maxw>>n;

// 输入每个物品的重量和价值
for(int i=1;i<=n;i++) cin>>w[i]>>p[i];

// 动态规划核心部分
for(int i=1;i<=n;i++){
    // 情况1：当前容量放不下第i个物品
    for(int j=1;j<w[i];j++) 
        dp[i][j]=dp[i-1][j];
    
    // 情况2：当前容量可以放下第i个物品
    for(int j=w[i];j<=maxw;j++){
        dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+p[i]);
    }
}

// 输出最大价值
cout<<dp[n][maxw];
return 0;

} 代码详解 为什么使用 #define int long long？

虽然本题的数据范围（maxw ≤ 20000，n ≤ 100）不需要使用 long long，但这是一个良好的编程习惯，可以防止数据范围扩大后出现整数溢出。

数组大小说明

w[N], p[N]：N = 2e6+10是为了兼容更大规模的数据，本题实际只需要 105

dp[105][20005]：第一维是物品数（最多100），第二维是背包容量（最多20000）

核心逻辑分析

两层循环：

外层循环​ i：依次处理每个物品

内层循环​ j：枚举所有可能的背包容量

对于每个物品 i：

当容量 j < w[i]时，物品放不进去，直接继承上一行的结果

当容量 j ≥ w[i]时，比较「不放」和「放」两种方案的价值，取较大值

复杂度分析

时间复杂度：O(n × maxw)≈ 100 × 20000 = 2×10⁶，完全可行

空间复杂度：O(n × maxw)，使用了二维数组

示例验证

输入：

复制 10 3 4 5 3 4 6 9 手动模拟DP过程

物品\容量

0

1

2

3

4

5

6

7

8

9

10

0(初始)

0

0

0

0

0

0

0

0

0

0

0

1(4,5)

0

0

0

0

5

5

5

5

5

5

5

2(3,4)

0

0

0

4

5

5

5

9

9

9

9

3(6,9)

0

0

0

4

5

5

9

9

9

14

14

最终结果：dp[3][10] = 14✅

优化建议

本题也可以使用滚动数组优化空间复杂度至 O(maxw)：

cpp 下载 复制 vector dp(maxw+1, 0); for(int i=1;i<=n;i++){ for(int j=maxw;j>=w[i];j--){ dp[j] = max(dp[j], dp[j-w[i]]+p[i]); } } cout << dp[maxw];

这样只需一维数组，且内层循环必须倒序，以保证每个物品只被选取一次。