01背包问题
2026-08-29 09:50:15
发布于：上海
29阅读
0回复
0点赞
背包DP
动态规划的经典应用-背包问题。
一般来说，就是给定一组有固定价值和固定重量的物品，以及一个承重量固定的背包，求在不超过背包最大承重的前提下，能放进背包里的物品的最大总价值。
动态规划（DP）类问题主要求解的步骤
1、划分阶段
2、确定状态
3、确定决策并写出转移方程式
贪心为什么错？
根本原因：贪心需要算性价比（单位重量的价值），但题中的物品不可分割，所以计算性价比来排序的策略是错的。
所以，可以考虑01搜索，对每个物品遍历“选 or 不选”两种情况，但是可能会超时。
背包问题分类：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])
答案：
一般来说，dp[n][m];
实现代码：
#include<bits/stdc++.h>
using namespace std;
int t,m;
int dp[105][1005];
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 时的最大价值。
全部评论 2
顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶 顶顶顶顶顶 顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶 顶顶 顶顶 顶顶顶顶顶 顶顶顶顶顶顶顶顶顶 顶顶顶 顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶 顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶2026-08-31 来自 上海
1
有帮助，赞一个