J组最后几个知识点之一：背包问题
2026-08-27 12:01:55
发布于：上海
4阅读
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;
}
这里空空如也
有帮助，赞一个