广东建设工程协会网站,专业的网站首页建设公司,wordpress 字号,wordpress theme 检测个人主页 #xff1a; zxctscl 如有转载请先通知 DP41 【模板】01背包 1. DP41 【模板】01背包2. 分析3. 代码4. 优化5. 优化后代码 1. DP41 【模板】01背包 2. 分析
一、题目解析#xff1a; 来看一下例1#xff0c;3代表有三个物品#xff0c;5代表能够容纳的体积。第一… 个人主页 zxctscl 如有转载请先通知 DP41 【模板】01背包 1. DP41 【模板】01背包2. 分析3. 代码4. 优化5. 优化后代码 1. DP41 【模板】01背包 2. 分析
一、题目解析 来看一下例13代表有三个物品5代表能够容纳的体积。第一行要求中并没有说把背包全部装满选择价值最大的就行而第二行输出要求的是装满时候的价值。 在体积是5条件下第一种可以选1号物品和3号物品它们价值就是10414第二种可以选择2号和3号它们价值就是549第一行输出没有要求背包装满所以选择第一种方式就行。 第二行输出是背包恰好装满的情况就选择第二种情况。 而输出背包必须装满的情况可能是不存在的就像例2 给的三个物品体积凑不出来体积为8的情况。
二、算法原理 1先来做第一行返回值 状态表示 以某一个位置为结尾 如果用dp[i]来表示从前i个物品中选择在所有选择中的最大价值但是还得考虑体积的大小。所以这里的状态表示是 dp[i][j]从从前i个物品中选择总体积不超过j的所有选择中能挑出来的最大价值。 状态转移方程 根据最后一步的状况分情况讨论。 第一种情况不选择i物品那么就是在i-1里面选择并且体积也依旧小于j,所以就是dp[i-1][j]
第二种情况选择i物品那么必须有w[i]实现的价值最大就得从i-1里面挑价值最大的出来并且此时体积要改变所以到这里的体积必须能够装下v[i]到i-1位置体积就必须小于j-v[i]所以这里的状态表示就是w[i]dp[i-1][j-v[i]] 然后求这两种情况下的最大值就可以了。 初始化 dp表从1开始计数就多了一行和一列。要保证第一行和第一列填表正确物品从0中选就是0体积从0中挑还是0所以初始化为0就行。 填表顺序 它依赖它的上一行位置i-1表示的是上一行从上往下 返回值
返回dp[n][v] 2先来做第一行返回值 状态表示 只需要v的位置正好等于j就行 dp[i][j]从从前i个物品中选择总体积正好等于j的所有选择中能挑出来的最大价值。 状态转移方程 第一种情况不选择i物品那么就是在i-1里面选择并且体积也依旧小于j,所以就是dp[i-1][j]但是这里j可能凑不到总体积就用一个dp[i][j]-1来表示这样的情况所以得先判断dp[i][j]是不是等于-1所以这种情况就不选择。
第二种情况选择i物品那么必须有w[i]实现的价值最大就得从i-1里面挑价值最大的出来并且此时体积要改变所以到这里的体积必须能够装下v[i]到i-1位置体积就必须小于j-v[i]但是这里必须判断dp[i][j]是不是等于-1所以这里的状态表示就是dp[i][j]不是等于-1情况下w[i]dp[i-1][j-v[i]] 初始化 第一个位置没有物品直接物品和体积都是0,第一行[0,1]位置没有物品想要凑成体积是1是不可能的所以第一行剩下的位置就初始化为-1。第一列表示想要把体积正好凑成0那么不选就是0就初始化为0就行 填表顺序 从上往下 返回值 先得判断一下dp[n][V]是不是等于-1如果是就返回0不是就返回dp[n][V]
3. 代码
#include cstring
#include iostreamusing namespace std;
const int N 1010;
int n, V, v[N], w[N];
int dp[N][N];int main() {cin n V;for (int i 1; i n; i)cin v[i] w[i];for (int i 1; i n; i) {for (int j 1; j V; j) {dp[i][j] dp[i - 1][j];if (j v[i])dp[i][j] max(dp[i][j], dp[i - 1][j - v[i]] w[i]);}}cout dp[n][V] endl;//第二问memset(dp, 0, sizeof dp);for (int j 1; j V; j)dp[0][j] -1;for (int i 1; i n; i) {for (int j 1; j V; j) {dp[i][j] dp[i - 1][j];if (j v[i]dp[i-1][j-v[i]]!-1) {dp[i][j] max(dp[i][j], dp[i - 1][j - v[i]] w[i]);}}}cout (dp[n][V]-1?0:dp[n][V]) endl;return 0;
}
// 64 位输出请用 printf(%lld)4. 优化
利用滚动数组做空间上的优化代码在原基础上修改即可
在填第i行的时候仅想要i-1行就可以。 就是说要填第1行的数据就需要第0行的数据第1行填完之后第0行就没有用了需要这一行变得有用就把这一行滚动到第2行然后利用第1行的值来填第2行以此类推就可以更新完这个dp表。 所有这里只需要用到数组就只用到一维。
遍历顺序要改为从右往左。 5. 优化后代码
删除所有横坐标遍历顺序从右往左
#include cstring
#include iostreamusing namespace std;
const int N 1010;
int n, V, v[N], w[N];
int dp[N];int main() {cin n V;for (int i 1; i n; i)cin v[i] w[i];for (int i 1; i n; i) {for (int j V; j v[i]; j--) dp[j] max(dp[j], dp[j - v[i]] w[i]);}cout dp[V] endl;//第二问memset(dp, 0, sizeof dp);for (int j 1; j V; j)dp[j] -1;for (int i 1; i n; i) {for (int j V; j v[i]; j--) if(dp[j-v[i]]!-1)dp[j] max(dp[j], dp[j - v[i]] w[i]);}cout (dp[V]-1?0:dp[V]) endl;return 0;
}
// 64 位输出请用 printf(%lld)注意
这些思路是可以套用到很多题目里面的。不要去强行解释优化后代码的状态表示及状态表示方程。
有问题请指出大家一起进步
