J组最后几个知识点之一：背包问题
2026-08-27 12:01:55
发布于：上海
26阅读
0回复
0点赞
· 动态规划的经典应用——背包问题：
一般来说，就是给定一组有固定价值和固定重量的物品，以及一个承重量固定的背包，求在不超过背包最大承重量的前提下，能放进背包里的物品的最大总价值。
· 动态规划（DP）类问题主要求解的步骤：
1.划分阶段
2.确定状态
3.确定决策并写出转移方程式
· 贪心为什么错：
根本原因：贪心需要算性价比（单位重量对应的价值），但题中的物品不可分割，所以计算性价比来排序的是错的。
所以，也可以考虑01搜索，对每个物品遍历“选或不选”两种情况，但是可能会超时。
背包问题的题型分类: 01背包，完全背包，多重背包，分组背包........
· 1.01背包
问题定义：有n件物品和一个容量为v的背包，第i件物品体积wi，价值vi，，每件物品只有一件，只能选或不选，求不超过容量的前提下能获得的最大总价值。
状态定义：
dp [ i ][ j ] 表示前 i 个物品，容量为 j 时的最大价值。
状态转移：
选第 i 件物品：则dp[ i ][ j ] = dp[ i - 1 ][ j - w[ i ] ] + v[ i ]
不选第 i 件物品：则 dp[ i ][ j ] = dp[ i - 1 ][ j ]
所以收益最大的是：
dp[ i ][ j ] = max( dp[ i - 1 ][ j - w[ i ] ] + v[ i ], dp[ i - 1][ j ] )
朴素代码实现
#include<bits/stdc++.h>
using namespace std;
//背包：识别重量和价值分别是谁
int t, m;//时间，数量
int dp[105][1005];//前i种草药，花费j时间能拿到的最大价值
int main(){
cin >> t >> m;
//遍历草药的种类
for(int i = 1; i <= m; i++){
int w, v;
cin >> w >> v;
//遍历时间（重量）
for(int j = 0; j <= t; j++){
if(j >= w) dp[i][j] = max(dp[i - 1][j - w] + v, dp[i - 1][j]);
else dp[i][j] = dp[i - 1][j];
}
}
cout << dp[m][t];
return 0;
}
滚动数组优化
每次都是覆盖上一行，尝试是否可以使用一维数组进行实现。
确定状态：dp[j] 表示背包容量为 j 时的最大价值。
#include<bits/stdc++.h>
using namespace std;
int n, m;
int dp[12885];//dp[j]：容量不超过 j 时的最大价值
int w[3500], d[3500];
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> w[i] >> d[i];
}
for(int i = 1; i <= n; i++){
//01背包，逆序遍历，保证每个物品只拿一次
for(int j = m; j >= w[i]; j--){
dp[j] = max(dp[j], dp[j - w[i]] + d[i]);
}
}
cout << dp[m];
return 0;
}
全部评论 1
顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶 顶顶顶顶顶 顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶 顶顶 顶顶 顶顶顶顶顶 顶顶顶顶顶顶顶顶顶 顶顶顶 顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶 顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶2026-08-31 来自 上海
2
有帮助，赞一个