前言
小偷不可怕,就怕小偷有文化,更怕小偷学过动态规划。
正文
白玉汤曾是江湖上赫赫有名的盗圣,奈何岁月不饶人,上了年纪后腿脚便不利索了,无奈一身的本领却没有个传承之人。这天,一位少年前来拜师学艺,希望白玉汤能在偷盗一事上指点一二。白玉汤见这少年骨骼清奇,内心有收其为徒的想法,便出了下面这道题考考少年:
话说地主金馆长家有个专门藏金银财宝的房间,潜入后发现可偷之物太多,奈何自身负重能力有限,你的包只能承重 20kg 的物品,而且每个物品的价值又都不一样,那么问题来了,将哪些物品装入背包才能不虚此行,使价值总和最大呢?物品重量和其价值的关系如下:
编号 | 重量(w) | 价值(v) |
---|---|---|
1 | 2 | 3 |
2 | 3 | 4 |
3 | 4 | 5 |
4 | 5 | 8 |
5 | 9 | 10 |
少年一看,这不就是一道“01 背包问题吗”,说完便在地上做出了如下分析:
设我们的背包里面的物品价值为 b,给背包添加两个参数:k 和 c,即 b(k,c),那么 b(k,c)又表示什么什么意思呢?
k 表示你面对的物品编号,即 1~5, c 表示你面对 k 号物品时,背包的剩余容量 b(k,c)表示面对 k 号物品,并作出拿或不拿的选择之后,背包里面的物品总价值
举个例子,b(2,20)表示的是,在你的背包容量为 20 的情况下,当你面对 2 号物品时并作出拿或者不拿的选择后,背包中物品的总价值。
了解了这个概念后我们继续: 假设你现在遇见了第 k 号物品,此时你的背包容量为 c,你得做出一个决策,到底要不要拿走第 k 件物品呢?那么拿不拿的前提是啥?当然是这个物品重不重,能不能塞到包里。所以第一种情况就出现了:
- 如果第 k 件物品的重量 w[k]比此时的背包的剩余重量 c 大了,那我肯定是拿不动了,即
w[k]>c
。所以此时包中物品的价值就是我拿的前一个物品之后包中的价值,即b(k,c)=b(k-1,c).
包中剩余空间不变,还是 c。
那么第二种情况,如果我拿得动第 k 件物品,即第 k 件物品的重量w[k]<c
,面对 k 号物品,无外乎两种选择,拿或者不拿,这时我就要根据拿走之后产生的效益进行决策了:
- 不拿 k 号物品,那么此时包中物品的总价值
b(k,c)=b(k-1,c)
,和第一种拿不动 k 号物品的一样。 - 拿走 k 号物品,那么此时包中物品的总价值
b(k,c)=b(k-1,c-w[k])+v[k]
拿了第 k 件物品后,那我的包中的价值肯定就是原先的价值再加上第 k 件物品的价值,而且拿了之后包中的剩余容量就为c-w[k]
了。 总结一下,就是如下的公式了:b(k,c)=max{b(k-1,c),b(k-1,c-w[k])+v[k]}
剩下的只需要比较小这两种方式谁的效益大即可。思维导图如下:
看懂以上描述后,编码就很简单了,这里我用 Java 写出来
class Main {
public static void main(String[] args) {
int[] w = { 0, 2, 3, 4, 5, 9 };
int[] v = { 0, 3, 4, 5, 8, 10 };
int N = 6, W = 21;
int[][] b = new int[N][W];
for (int k = 1; k < N; k++) {
for (int c = 1; c < W; c++) {
if (w[k] > c) {
b[k][c] = b[k - 1][c];
} else {
int value1 = b[k - 1][c - w[k]] + v[k]; // 拿第k件物品
int value2 = b[k - 1][c]; // 不拿第k件物品
b[k][c] = Math.max(value1, value2);
}
}
}
System.out.println(b[5][20]);
}
}
结果为 26
最后
其实公众号之前有发过一篇类似的“01 背包问题”的解析——《使用动态规划解决童年难题》,网上大多数的博客在解析“01 背包问题”时也都是采用画图的形式,类似于这样的: 但是我当时看的时候真的是一脸懵逼,然后再带着图去看长篇的解析就更混乱了。希望你能在理解了上述流程之后,再回过头去看公众号之前的文章,对那个图的理解应该就会更加深刻了,二者一起看,辅助理解。
推荐
- 推荐一个良心视频,讲解的也很详细——01 背包问题
- 推荐一个在线查看解决“01 背包问题”的网站,详细的描述了变化过程Online 0/1 Knapsack problem solver
如果你觉得本文还不错,麻烦随手点赞与转发吧。😋(扑通
点赞与转发是最好的支持