一个背着背包的小偷闯空门偷东西,他必须趁屋主回来之前把有价值的物品塞进包包内带走。考虑到小偷自身的行动力,背包能装的物品总重量有限,小偷要如何选择物品才能获得最高的总价值?
这篇文章将会直接以动态规划来解决问题,如果您还不熟悉动态规划的话可以先查看这篇文章:
假设房屋内有以下几项物品:
- 一支价值为 1200 元的石英表,重 200 公克。
- 一支价值为 1500 元的手机,重 500 公克。
- 一幅价值为 1500 元的画,重 300 公克。
- 一台价值为 4000 元的平板电脑,重 850 公克。
而背包最多只能放 1 公斤,也就是 1000 公克。
在塞满背包的条件下,小偷可以怎么偷?
- 平板电脑。(4000 元,850 公克)
- 石英表、手机、画。(4200 元,1000 公克)
显然,小偷要偷「石英表、手机、画」才可以让背包拥有最高的价值。当然这类问题不是只要选择最多的物品数量(从重量最轻的物品开始选),总价值就一定最高;也不是只要从价值最高的物品开始选,总价值就一定最高。如果物品的种类多了,就不像上面这样可以轻易地列出组合方式,找出拥有最高总价值的组合。
以 Top-down 的方式来思考上面的问题。逐一去看各个物品,来决定要不要(或是能不能)将其放进背包。假设愈贵的物品愈先看,那么最后小偷得决定要不要把石英表放进背包,如果要放,那么背包内的总价值就会是判断完上一个物品要不要放进背包的价值再加上石英表的价值;如果不要放,那么背包内的总价值就会是判断完上一个物品要不要放进背包的价值。而如果小偷在最后阶段放了石英表,则上一个物品在判断要不要被放进背包时,最大重量就必须要再减掉石英表的 200 公克(如此才能保证最后一次有办法把石英表放进包包)……其余阶段也依此类推。最小的问题为看完物品了(没有物品能放,价值为 0)。
至于在每个阶段要如何决定物品要不要放进背包,首先就去看物品的重量,如果还放得下的话,就去判断把物品放进背包,和不要把物品放进背包时的价值哪个大,若前者大,当然就是放进背包;若后者大,当然就是不放进背包。
以程序来解题的话,我们可以写出以下的递归函数:
fn knapsack_inner(item_values: &[usize], item_weight: &[usize], max_weight: usize, ith: usize) -> usize {
if ith == item_values.len() {
0
} else {
let weight = item_weight[ith];
let not_put = knapsack_inner(item_values, item_weight, max_weight, ith + 1);
if weight > max_weight {
not_put
} else {
let put = knapsack_inner(item_values, item_weight, max_weight - weight, ith + 1) + item_values[ith];
not_put.max(put)
}
}
}
pub fn knapsack(item_values: &[usize], item_weight: &[usize], max_weight: usize) -> usize {
knapsack_inner(item_values, item_weight, max_weight, 0)
}
static int knapsackInner(final int[] itemValues, final int[] itemWeight, final int maxWeight, final int ith) {
if (ith == itemValues.length) {
return 0;
} else {
final int weight = itemWeight[ith];
final int notPut = knapsackInner(itemValues, itemWeight, maxWeight, ith + 1);
if (weight > maxWeight) {
return notPut;
} else {
final int put = knapsackInner(itemValues, itemWeight, maxWeight - weight, ith + 1) + itemValues[ith];
return Math.max(notPut, put);
}
}
}
public static int knapsack(final int[] itemValues, final int[] itemWeight, final int maxWeight) {
return knapsackInner(itemValues, itemWeight, maxWeight, 0);
}
function knapsackInner(itemValues: number[], itemWeight: number[], maxWeight: number, ith: number): number {
if (ith === itemValues.length) {
return 0;
} else {
const weight = itemWeight[ith];
const notPut = knapsackInner(itemValues, itemWeight, maxWeight, ith + 1);
if (weight > maxWeight) {
return notPut;
} else {
const put = knapsackInner(itemValues, itemWeight, maxWeight - weight, ith + 1) + itemValues[ith];
return Math.max(notPut, put);
}
}
}
function knapsack(itemValues: number[], itemWeight: number[], maxWeight: number) {
return knapsackInner(itemValues, itemWeight, maxWeight, 0);
}
func knapsackInner(itemValues []int, itemWeight []int, maxWeight int, ith int) int {
if ith == len(itemValues) {
return 0
} else {
weight := itemWeight[ith]
notPut := knapsackInner(itemValues, itemWeight, maxWeight, ith+1)
if weight > maxWeight {
return notPut
} else {
put := knapsackInner(itemValues, itemWeight, maxWeight-weight, ith+1) + itemValues[ith]
if put > notPut {
return put
} else {
return notPut
}
}
}
}
func Knapsack(itemValues []int, itemWeight []int, maxWeight int) int {
return knapsackInner(itemValues, itemWeight, maxWeight, 0)
}
由于以上代码有重叠子问题,所以可以用动态规划的记忆法来优化或是用制表法将其改写成迭代函数。
以制表法为例,改写如下:
pub fn knapsack(item_values: &[usize], item_weight: &[usize], max_weight: usize) -> usize {
let mut dp = vec![vec![0; item_values.len() + 1]; max_weight + 1];
for (ith, weight) in item_weight.iter().copied().enumerate().rev() {
for mw in 0..=max_weight {
let not_put = dp[mw][ith + 1];
if weight > mw {
dp[mw][ith] = not_put;
} else {
let put = dp[mw - weight][ith + 1] + item_values[ith];
if put > not_put {
dp[mw][ith] = put;
} else {
dp[mw][ith] = not_put;
}
}
}
}
dp[max_weight][0]
}
以上程序,故意不使用编程语言内置的 max 函数来取大值,因为之后如果要取得背包内到底放了什么东西,我们会需要在 if 区块内添加程序叙述。
public static int knapsack(final int[] itemValues, final int[] itemWeight, final int maxWeight) {
final int[][] dp = new int[maxWeight + 1][itemValues.length + 1];
for (int ith = itemWeight.length - 1; ith >= 0; --ith) {
final int weight = itemWeight[ith];
for (int mw = 0; mw <= maxWeight; ++mw) {
final int notPut = dp[mw][ith + 1];
if (weight > mw) {
dp[mw][ith] = notPut;
} else {
final int put = dp[mw - weight][ith + 1] + itemValues[ith];
if (put > notPut) {
dp[mw][ith] = put;
} else {
dp[mw][ith] = notPut;
}
}
}
}
return dp[maxWeight][0];
}
以上程序,故意不使用编程语言内置的 max 函数来取大值,因为之后如果要取得背包内到底放了什么东西,我们会需要在 if 区块内添加程序叙述。
function knapsack(itemValues: number[], itemWeight: number[], maxWeight: number) {
const dp = new Array<number[]>(maxWeight + 1);
const itemCountInc = itemValues.length + 1;
for (let i = 0;i <= maxWeight;i++) {
dp[i] = new Array<number>(itemCountInc).fill(0);
}
for (let ith = itemWeight.length - 1;ith >= 0;ith--) {
const weight = itemWeight[ith];
for (let mw = 0;mw <= maxWeight;mw++) {
const notPut = dp[mw][ith + 1];
if (weight > mw) {
dp[mw][ith] = notPut;
} else {
const put = dp[mw - weight][ith + 1] + itemValues[ith];
if (put > notPut) {
dp[mw][ith] = put;
} else {
dp[mw][ith] = notPut;
}
}
}
}
return dp[maxWeight][0];
}
以上程序,故意不使用编程语言内置的 max 函数来取大值,因为之后如果要取得背包内到底放了什么东西,我们会需要在 if 区块内添加程序叙述。
func Knapsack(itemValues []int, itemWeight []int, maxWeight int) int {
dp := make([][]int, maxWeight+1)
itemCountInc := len(itemValues) + 1
for i := 0; i <= maxWeight; i++ {
dp[i] = make([]int, itemCountInc)
}
for ith := len(itemWeight) - 1; ith >= 0; ith -= 1 {
weight := itemWeight[ith]
for mw := 0; mw <= maxWeight; mw += 1 {
notPut := dp[mw][ith+1]
if weight > mw {
dp[mw][ith] = notPut
} else {
put := dp[mw-weight][ith+1] + itemValues[ith]
if put > notPut {
dp[mw][ith] = put
} else {
dp[mw][ith] = notPut
}
}
}
}
return dp[maxWeight][0]
}
观察以上程序,可以发现 dp 数组能简化成长度为 max_weight + 1 或 maxWeight + 1 的一维数组。
程序继续优化如下:
pub fn knapsack(item_values: &[usize], item_weight: &[usize], max_weight: usize) -> usize {
let mut dp = vec![0; max_weight + 1];
for (ith, weight) in item_weight.iter().copied().enumerate() {
for mw in (weight..=max_weight).rev() {
let not_put = dp[mw];
let put = dp[mw - weight] + item_values[ith];
if put > not_put {
dp[mw] = put;
} else {
dp[mw] = not_put;
}
}
}
dp[max_weight]
}
public static int knapsack(final int[] itemValues, final int[] itemWeight, final int maxWeight) {
final int[] dp = new int[maxWeight + 1];
for (int ith = 0; ith < itemWeight.length; ++ith) {
final int weight = itemWeight[ith];
for (int mw = maxWeight; mw >= weight; --mw) {
final int notPut = dp[mw];
final int put = dp[mw - weight] + itemValues[ith];
if (put > notPut) {
dp[mw] = put;
} else {
dp[mw] = notPut;
}
}
}
return dp[maxWeight];
}
function knapsack(itemValues: number[], itemWeight: number[], maxWeight: number) {
const dp = new Array<number>(maxWeight + 1).fill(0);
for (let ith = 0;ith < itemWeight.length;ith++) {
const weight = itemWeight[ith];
for (let mw = maxWeight;mw >= weight;--mw) {
const notPut = dp[mw];
const put = dp[mw - weight] + itemValues[ith];
if (put > notPut) {
dp[mw] = put;
} else {
dp[mw] = notPut;
}
}
}
return dp[maxWeight];
}
func Knapsack(itemValues []int, itemWeight []int, maxWeight int) int {
dp := make([]int, maxWeight+1)
for ith, weight := range itemWeight {
for mw := maxWeight; mw >= weight; mw -= 1 {
notPut := dp[mw]
put := dp[mw-weight] + itemValues[ith]
if put > notPut {
dp[mw] = put
} else {
dp[mw] = notPut
}
}
}
return dp[maxWeight]
}
而以上程序,又可以再优化成:
pub fn knapsack(item_values: &[usize], item_weight: &[usize], max_weight: usize) -> usize {
let mut dp = vec![0; max_weight + 1];
for mw in item_weight[0]..=max_weight {
dp[mw] = item_values[0];
}
for (ith, weight) in item_weight[1..].iter().copied().enumerate() {
for mw in (weight..=max_weight).rev() {
let not_put = dp[mw];
let put = dp[mw - weight] + item_values[ith + 1];
if put > not_put {
dp[mw] = put;
} else {
dp[mw] = not_put;
}
}
}
dp[max_weight]
}
public static int knapsack(final int[] itemValues, final int[] itemWeight, final int maxWeight) {
final int[] dp = new int[maxWeight + 1];
for (int mw = maxWeight; mw >= itemWeight[0]; --mw) {
dp[mw] = itemValues[0];
}
for (int ith = 1; ith < itemWeight.length; ++ith) {
final int weight = itemWeight[ith];
for (int mw = maxWeight; mw >= weight; --mw) {
final int notPut = dp[mw];
final int put = dp[mw - weight] + itemValues[ith];
if (put > notPut) {
dp[mw] = put;
} else {
dp[mw] = notPut;
}
}
}
return dp[maxWeight];
}
function knapsack(itemValues: number[], itemWeight: number[], maxWeight: number) {
const dp = new Array<number>(maxWeight + 1).fill(0);
for (let mw = maxWeight;mw >= itemWeight[0];mw--) {
dp[mw] = itemValues[0];
}
for (let ith = 1;ith < itemWeight.length;ith++) {
const weight = itemWeight[ith];
for (let mw = maxWeight;mw >= weight;mw--) {
const notPut = dp[mw];
const put = dp[mw - weight] + itemValues[ith];
if (put > notPut) {
dp[mw] = put;
} else {
dp[mw] = notPut;
}
}
}
return dp[maxWeight];
}
func Knapsack(itemValues []int, itemWeight []int, maxWeight int) int {
dp := make([]int, maxWeight+1)
for mw := maxWeight; mw >= itemWeight[0]; mw -= 1 {
dp[mw] = itemValues[0]
}
for ith, weight := range itemWeight[1:] {
for mw := maxWeight; mw >= weight; mw -= 1 {
notPut := dp[mw]
put := dp[mw-weight] + itemValues[ith+1]
if put > notPut {
dp[mw] = put
} else {
dp[mw] = notPut
}
}
}
return dp[maxWeight]
}
想要知道背包里到底放了哪些物品,以我们目前使用的 dp 一维数组算法并不太容易做到。大概就是要创建出一个二维数组,去记录在所有的最大重量以及物品下,该物品有没有被放进背包,最后再反推回去找到所有被放进背包的物品。而如果是用之前的 dp 二维数组,则可以直接反推放进背包的物品。
dp[w][ith] 表示在最大重量为 w 时,放或不放 ith 物品的最大价值(ith 从 0 开始放),以 v 来表示。要判断这个 ith 物品到底有没有被放进去,就去看 dp[w][ith + 1] 是否与 dp[w][ith] 相等,相等表示没有放,不相等表示有放。若是没放,继续看下一个 ith;若是有放,则减少最大重量 w 和价值 v 后,再去看下一个 ith。如果价值 v 被减为 0 了,表示背包内的东西都已经找出来了。
程序如下:
pub fn knapsack(item_values: &[usize], item_weight: &[usize], max_weight: usize) {
let mut dp = vec![vec![0; item_values.len() + 1]; max_weight + 1];
for (ith, weight) in item_weight.iter().copied().enumerate().rev() {
for mw in 0..=max_weight {
let not_put = dp[mw][ith + 1];
if weight > mw {
dp[mw][ith] = not_put;
} else {
let put = dp[mw - weight][ith + 1] + item_values[ith];
if put > not_put {
dp[mw][ith] = put;
} else {
dp[mw][ith] = not_put;
}
}
}
}
let mut k = vec![];
let mut v = dp[max_weight][0];
let mut w = max_weight;
let mut ith = 0;
while v > 0 {
if dp[w][ith] != dp[w][ith + 1] {
k.push(ith);
v -= item_values[ith];
w -= item_weight[ith];
}
ith += 1;
}
println!("Put: {:?}, total value: {}", &k, dp[max_weight][0]);
}
public static void knapsack(final int[] itemValues, final int[] itemWeight, final int maxWeight) {
final int[][] dp = new int[maxWeight + 1][itemValues.length + 1];
for (int ith = itemWeight.length - 1; ith >= 0; --ith) {
final int weight = itemWeight[ith];
for (int mw = 0; mw <= maxWeight; ++mw) {
final int notPut = dp[mw][ith + 1];
if (weight > mw) {
dp[mw][ith] = notPut;
} else {
final int put = dp[mw - weight][ith + 1] + itemValues[ith];
if (put > notPut) {
dp[mw][ith] = put;
} else {
dp[mw][ith] = notPut;
}
}
}
}
final ArrayList<Integer> k = new ArrayList<>();
int v = dp[maxWeight][0];
int w = maxWeight;
int ith = 0;
while (v > 0) {
if (dp[w][ith] != dp[w][ith + 1]) {
k.add(ith);
v -= itemValues[ith];
w -= itemWeight[ith];
}
++ith;
}
System.out.printf("Put: %s, total value: %d%n", k.toString(), dp[maxWeight][0]);
}
function knapsack(itemValues: number[], itemWeight: number[], maxWeight: number) {
const dp = new Array<number[]>(maxWeight + 1);
const itemCountInc = itemValues.length + 1;
for (let i = 0;i <= maxWeight;i++) {
dp[i] = new Array<number>(itemCountInc).fill(0);
}
for (let ith = itemWeight.length - 1;ith >= 0;ith--) {
const weight = itemWeight[ith];
for (let mw = 0;mw <= maxWeight;mw++) {
const notPut = dp[mw][ith + 1];
if (weight > mw) {
dp[mw][ith] = notPut;
} else {
const put = dp[mw - weight][ith + 1] + itemValues[ith];
if (put > notPut) {
dp[mw][ith] = put;
} else {
dp[mw][ith] = notPut;
}
}
}
}
const k = [];
let v = dp[maxWeight][0];
let w = maxWeight;
let ith = 0;
while (v > 0) {
if (dp[w][ith] !== dp[w][ith + 1]) {
k.push(ith);
v -= itemValues[ith];
w -= itemWeight[ith];
}
ith += 1;
}
console.log(`Put: [${k.join(", ")}], total value: ${dp[maxWeight][0]}`);
}
func Knapsack(itemValues []int, itemWeight []int, maxWeight int) {
dp := make([][]int, maxWeight+1)
itemCountInc := len(itemValues) + 1
for i := 0; i <= maxWeight; i++ {
dp[i] = make([]int, itemCountInc)
}
for ith := len(itemWeight) - 1; ith >= 0; ith -= 1 {
weight := itemWeight[ith]
for mw := 0; mw <= maxWeight; mw += 1 {
notPut := dp[mw][ith+1]
if weight > mw {
dp[mw][ith] = notPut
} else {
put := dp[mw-weight][ith+1] + itemValues[ith]
if put > notPut {
dp[mw][ith] = put
} else {
dp[mw][ith] = notPut
}
}
}
}
k := make([]int, 0)
v := dp[maxWeight][0]
w := maxWeight
ith := 0
for v > 0 {
if dp[w][ith] != dp[w][ith+1] {
k = append(k, ith)
v -= itemValues[ith]
w -= itemWeight[ith]
}
ith++
}
fmt.Printf("Put %s, total value: %d\n", strings.Replace(fmt.Sprint(k), " ", ", ", -1), dp[maxWeight][0])
}
