背包DP(一)
2026-08-27 11:56:59
发布于:上海
·动态规划的经典应用-背包问题
·一般来说,就是给定一组有固定价值和固定重量的物品,以及一个承重量固定的背包,求在不超过背包最大承重量的前提下,能放进背包里面的物品的最大总价值。
·动态规划(dp)类问题主要求解的步骤:
·1.划分阶段
·2.确定状态
·3.确定决策并写出状态转移方程式
·01背包问题:每个问题只有一件,对每个物体只能选择拿或不拿
Q:用贪心为什么错误?
A:贪心需要算性价比(单位重量对应的价值),但题目中物体不可分割,所以计算性价比的排列策略错误
Q:也可以考虑01搜索,对每个物品遍历“选或不选”两种情况吗?
A:√,但是可能会超时
背包问题题型分类:01背包,完全背包,多重背包,分组背包......(j组只涉及前两个)
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][j]=dp[i-1][j-w[i]]+v[i] , dp[i][j]=dp[i-1][j])
输出答案
一般为dp[n][m]
这里空空如也












有帮助,赞一个