做小偷也要会动态规划——轻松解决"01背包问题"
前言 小偷不可怕，就怕小偷有文化，更怕小偷学过动态规划。 正文 白玉汤曾是江湖上赫赫有名的盗圣，奈何岁月不饶人，上了年纪后腿脚便不利索了，无奈一身的本领却没有个传承之人。这天，一位少年前来拜师学艺，希望白玉汤能在偷盗一事上指点一二。白玉汤见这少年骨骼清奇，内心有收其为徒的想法，便出了下面这道题考考少年： 话说地主金馆长家有个专门藏金银财宝的房间，潜入后发现可偷之物太多，奈何自身负重能力有限，你的包只能承重 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 号物品时并作出拿或者不拿的选择后，背包中物品的总价值。...