用動態規劃解決問題：零壹背包問題(0/1 Knapsack Problem)

一個背著背包的小偷闖空門偷東西，他必須趁屋主回來之前把有價值的物品塞進包包內帶走。考慮到小偷自身的行動力，背包能裝的物品總重量有限，小偷要如何選擇物品才能獲得最高的總價值？

這篇文章將會直接以動態規劃來解決問題，如果您還不熟悉動態規劃的話可以先查看這篇文章：

https://magiclen.org/dynamic-programming-basic/

假設房屋內有以下幾項物品：

一支價值為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 not_put
		} else {
			put := knapsackInner(itemValues, itemWeight, maxWeight-weight, ith+1) + itemValues[ith]

			if put > notPut {
				return put
			} else {
				return not_put
			}
		}
	}
}

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).rev().step_by(item_weight[0]) {
        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 -= itemWeight[0]) {
        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 -= itemWeight[0]) {
        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])
}