說明
假設有一個背包的負重最多可達8公斤，而希望在背包中裝入負重範圍內可得之總價物品，假設是水果好了，水果的編號、單價與重量如下所示：| 0 | 李子 | 4KG | NT$4500 |
| 1 | 蘋果 | 5KG | NT$5700 |
| 2 | 橘子 | 2KG | NT$2250 |
| 3 | 草莓 | 1KG | NT$1100 |
| 4 | 甜瓜 | 6KG | NT$6700 |
解法
背包問題是關於最佳化的問題，可以使用「動態規劃」（Dynamic programming），試著解決構成的大問題之小問題，基於小問題的最佳解答來解決大問題，最後得到的就是大問題的最佳解。以背包問題為例，要解決背包負重為8公斤，可能的水果有5個的最佳化問題，可以先解決背包負重為1公斤，可能的水果有1個的問題，接著解決背包負重為2公斤，可能的水果有1個的問題，然後解決背包負重為3公斤，可能的水果有1個的問題...
我們使用兩個陣列value與item，value表示目前負重下可得的最大總價，一開始都是0，item表示最後放至背包的水果，首先是只有李子，從可以負重1公斤到可以負重8公斤，能得到的最大總價各是：
| 背包負重 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| value | 0 | 0 | 0 | 4500 | 4500 | 4500 | 4500 | 9000 |
| item | － | － | － | 0 | 0 | 0 | 0 | 0 |
只有李子的情況下，可以直覺地寫出以上的表格，不過撰寫程式需要的不是直覺，而是演算的方式，做法是在負重3公斤以下時，不可能放入李子，總價皆為0，4公斤時可以放入一個李子，價值為4500元，還可以負擔0公斤，對應的價值為0元，4500+0的總價大於目前對應的value值，於是更新value與item；類似地，5公斤時可以放入一個李子，價值為4500元，還可以負擔1公斤，對應的價值為0元，4500+0的總價大於目前對應的value值，於是更新…8公斤時可以放入一個李子，價值為4500元，還可以負擔4公斤，對應的價值為4500元，4500+4500的總價大於目前對應的value值，於是更新。
因此在可以負重8公斤，只有李子的情況下，可以得到的最大總價是9000元，最後放入的李子是4公斤，裝入這顆李子前，背包能負重的是4公斤的水果，4公斤處對應的水果是李子，因此目前最佳解為9000元，兩顆李子。
接著處理背包負重為1公斤，可能的水果有2個的問題，背包負重為2公斤，可能的水果有2個的問題，背包負重為3公斤，可能的水果有2個的問題...因為方才已經處理過只有李子的運算，現在可以基於其結果，直接考慮該如何置入蘋果。
負重4公斤以下的情況，不可能放入蘋果，對應的value、item都不用更新，負重5公斤時，若先放入蘋果，表示只剩下1公斤負重，目前對應的value為0元，5700+0大於目前5公斤對應的value值4500，於是予以更新value與item，負重6、7時也都是這麼運算，負重8公斤時，若先放入蘋果，表示只剩下3公斤負重，對應的value為0元，0+5700不大於目前的value值9000，於是不更新。
| 背包負重 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| value | 0 | 0 | 0 | 4500 | 5700 | 5700 | 5700 | 9000 |
| item | － | － | － | 0 | 1 | 1 | 1 | 0 |
因此在可以負重8公斤，只有李子、蘋果的情況下，可以得到的最大總價是9000元，最後放入的李子是4公斤，裝入這顆李子前，背包能負重的是4公斤的水果，4公斤處對應的水果是李子，因此目前最佳解為9000元，兩顆李子。
接著處理背包負重為1公斤，可能的水果有3個的問題，背包負重為2公斤，可能的水果有3個的問題，背包負重為3公斤，可能的水果有3個的問題...因為方才已經處理過只有李子、蘋果的運算，現在可以基於其結果，直接考慮該如何置入橘子，依方才的演算方式，可以得到：
| 背包負重 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| value | 0 | 2250 | 2250 | 4500 | 5700 | 6750 | 7950 | 9000 |
| item | － | 2 | 2 | 0 | 1 | 2 | 2 | 0 |
接著基於以上，處理加上草莓的情況：
| 背包負重 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| value | 1100 | 2250 | 3350 | 4500 | 5700 | 6800 | 7950 | 9050 |
| item | 3 | 2 | 3 | 0 | 1 | 3 | 2 | 3 |
接著基於以上，處理加上甜瓜的情況：
| 背包負重 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| value | 1100 | 2250 | 3350 | 4500 | 5700 | 6800 | 7950 | 9050 |
| item | 3 | 2 | 3 | 0 | 1 | 3 | 2 | 3 |
由最後一個表格，可以得知在背包負重8公斤時，最多可以裝入9050元的水果，而最後一個裝入的水果是3號，也就是草莓，裝入了草莓，背包只能再放入7公斤的水果，所以必須看背包負重7公斤時的最佳解，最後一個放入的是2號，也就是橘子，現在背包剩下負重量5公斤，所以看負重5公斤的最佳解，最後放入的是1號，也就是蘋果，此時背包負重量剩下0公斤，無法再放入水果，所以求出最佳解為放入草莓、橘子與蘋果，而總價為9050元。
實作：Toy C Java Python Scala Ruby JavaScript Haskell
from '/lib/math' import min
class Fruit {
def init(name, weight, price) {
this.name = name
this.weight = weight
this.price = price
}
def toString() {
return '{{0}:{1}w:${2}}'.format(this.name, this.weight, this.price)
}
}
def knapsack(fruits, values, items, limit) {
(iterate(0, fruits.length()).forEach(i ->
iterate(fruits.get(i).weight, limit + 1).forEach(w ->
trySolution(i, w, fruits, values, limit)
)
))
}
def trySolution(i, w, fruits, values, limit) {
p = w - fruits.get(i).weight
newValue = values.get(p) + fruits.get(i).price
if newValue > values.get(w) {
values.set(w, newValue)
items.set(w, i)
}
}
(fruits = [
new Fruit('李子', 4, 4500),
new Fruit('蘋果', 5, 5700),
new Fruit('橘子', 2, 2250),
new Fruit('草莓', 1, 1100),
new Fruit('甜瓜', 6, 6700)
])
WEIGHT_LIMIT = 8
items = List.create(WEIGHT_LIMIT, 0)
values = List.create(WEIGHT_LIMIT, 0)
def fruit(i) {
return fruits.get(items.get(i))
}
knapsack(fruits, values, items, WEIGHT_LIMIT)
min_weight = min(fruits.map(fruit -> fruit.weight))
(iterate(WEIGHT_LIMIT, i -> i >= min_weight, i -> i - fruit(i).weight)
.forEach(i -> println(fruit(i))))
println('${0}'.format(values.get(WEIGHT_LIMIT)))#include <stdio.h>
#include <stdlib.h>
#define LIMIT 8 // 重量限制
typedef struct {
char name[20];
int weight;
int price;
} Fruit;
void knapsack(Fruit*, int*, int*, int, int);
int min(Fruit*, int);
int main(void) {
Fruit fruits[] = {{"李子", 4, 4500},
{"蘋果", 5, 5700},
{"橘子", 2, 2250},
{"草莓", 1, 1100},
{"甜瓜", 6, 6700}};
int items[LIMIT + 1] = {0};
int values[LIMIT + 1] = {0};
int length = sizeof(fruits) / sizeof(fruits[0]);
knapsack(fruits, values, items, length, LIMIT);
printf("物品\t價格\n");
int i;
for(i = LIMIT; i >= min(fruits, length); i -= fruits[items[i]].weight) {
printf("%s\t%d\n", fruits[items[i]].name, fruits[items[i]].price);
}
printf("合計\t%d\n", values[LIMIT]);
return 0;
}
void knapsack(Fruit* fruits, int* values, int* items,
int length, int limit) {
int i, w;
for(i = 0; i < length; i++) {
for(w = fruits[i].weight; w <= limit; w++) {
int p = w - fruits[i].weight;
int newValue = values[p] + fruits[i].price;
if(newValue > values[w]) { // 找到階段最佳解
values[w] = newValue;
items[w] = i;
}
}
}
}
int min(Fruit* fruits, int length) {
int i, m;
for(i = 0, m = fruits[0].weight; i < length; i++) {
if(fruits[i].weight < m) {
m = fruits[i].weight;
}
}
return m;
}
import java.util.*;
class Fruit {
String name;
int weight;
int price;
Fruit(String name, int weight, int price) {
this.name = name;
this.weight = weight;
this.price = price;
}
public String toString() {
return String.format("(%s, %d, %d)", name, weight, price);
}
}
public class Knapsack {
public static List<Fruit> knapsack(List<Fruit> fruits, int limit) {
int[] values = new int[limit + 1];
int[] items = new int[limit + 1];
for(int i = 0; i < fruits.size(); i++) {
for(int w = fruits.get(i).weight; w <= limit; w++) {
int p = w - fruits.get(i).weight;
int newValue = values[p] + fruits.get(i).price;
if(newValue > values[w]) {
values[w] = newValue;
items[w] = i;
}
}
}
List<Fruit> solution = new ArrayList<>();
// JDK8 Lambda
int min = Collections.min(fruits
, (f1, f2) -> f1.weight - f2.weight).weight;
for(int i = limit; i >= min; i -= fruits.get(items[i]).weight) {
solution.add(fruits.get(items[i]));
}
return solution;
}
public static void main(String[] args) {
System.out.println(knapsack(Arrays.asList(
new Fruit("李子", 4, 4500), new Fruit("蘋果", 5, 5700),
new Fruit("橘子", 2, 2250), new Fruit("草莓", 1, 1100),
new Fruit("甜瓜", 6, 6700)), 8));
}
}from functools import reduce
def knapsack(fruits, limit):
def nextVI(i, values, items):
return reduce(
(lambda vis, vi: (vis[0] + [vi[0]], vis[1] + [vi[1]])),
[(values[w - fruits[i][1]] + fruits[i][2], i)
if w >= fruits[i][1] and w < limit + 1 and
values[w - fruits[i][1]] + fruits[i][2] > values[w]
else (values[w], items[w]) for w in range(len(values))],
([], [])
)
def iterate(i):
if i == 0:
return nextVI(i, [0] * (limit + 1), [0] * (limit + 1))
else:
values, items = iterate(i - 1)
return nextVI(i, values, items)
def solution(i, items, minWeight):
return (([fruits[items[i]]] +
solution(i - fruits[items[i]][1], items, minWeight))
if i >= minWeight else [])
return solution(limit,
iterate(len(fruits) - 1)[1], min([f[1] for f in fruits]))
print(knapsack([('李子', 4, 4500), ('蘋果', 5, 5700),
('橘子', 2, 2250), ('草莓', 1, 1100),
('甜瓜', 6, 6700)], 8))case class Fruit(name: String, weight: Int, price: Int)
def knapsack(fruits: List[Fruit], limit: Int) = {
def nextVI(i: Int, values: List[Int], items: List[Int]) = {
val viList = (for(w <- 0 until values.size) yield
if(w >= fruits(i).weight && w < limit + 1 &&
values(w - fruits(i).weight) + fruits(i).price > values(w))
(values(w - fruits(i).weight) + fruits(i).price, i)
else (values(w), items(w)))
((Nil : List[Int], Nil : List[Int]) /: viList) {
(vis: (List[Int], List[Int]), vi: (Int, Int))
=> (vis._1 ++ List(vi._1), vis._2 ++ List(vi._2))
}
}
def iterate(i: Int): (List[Int], List[Int]) = {
if(i == 0) {
val arr = new Array[Int](limit + 1)
nextVI(i, arr.toList, arr.toList)
} else {
val (values, items) = iterate(i - 1)
nextVI(i, values, items)
}
}
case class Fruit(name: String, weight: Int, price: Int)
def knapsack(fruits: List[Fruit], limit: Int) = {
def nextVI(i: Int, values: List[Int], items: List[Int]) = {
val viList = (for(w <- 0 until values.size) yield
if(w >= fruits(i).weight && w < limit + 1 &&
values(w - fruits(i).weight) + fruits(i).price > values(w))
(values(w - fruits(i).weight) + fruits(i).price, i)
else (values(w), items(w)))
(viList :\ (Nil : List[Int], Nil : List[Int])) {
(vi: (Int, Int), vis: (List[Int], List[Int]))
=> (vi._1 :: vis._1, vi._2 :: vis._2)
}
}
def iterate(i: Int): (List[Int], List[Int]) = {
if(i == 0) {
val arr = new Array[Int](limit + 1)
nextVI(i, arr.toList, arr.toList)
} else {
val (values, items) = iterate(i - 1)
nextVI(i, values, items)
}
}
def solution(i: Int, items: List[Int], minWeight: Int): List[Fruit] = {
if(i >= minWeight)
fruits(items(i)) :: solution(
i - fruits(items(i)).weight, items, minWeight)
else Nil
}
solution(limit, iterate(fruits.size - 1)._2,
fruits.map(fruit => fruit.weight).min)
}
println(knapsack(List(Fruit("李子", 4, 4500), Fruit("蘋果", 5, 5700),
Fruit("橘子", 2, 2250), Fruit("草莓", 1, 1100),
Fruit("甜瓜", 6, 6700)), 8))
# encoding: Big5
def knapsack(fruits, limit)
nextVI = ->(i, values, items) {
(0...values.size).map { |w|
if w >= fruits[i][:weight] and w < limit + 1 and
values[w - fruits[i][:weight]] + fruits[i][:price] > values[w]
{value: values[w - fruits[i][:weight]] + fruits[i][:price],
item: i}
else
{value: values[w], item: items[w]}
end
}.reduce({values: [], items: []}) { |vis, vi|
{values: vis[:values] + [vi[:value]],
items: vis[:items] + [vi[:item]]}
}
}
iterate = ->(i) {
if i == 0
nextVI.call(i, [0] * (limit + 1), [0] * (limit + 1))
else
vis = iterate.call(i - 1)
nextVI.call(i, vis[:values], vis[:items])
end
}
solution = ->(i, items, minWeight) {
if i >= minWeight
[fruits[items[i]]] +
solution.call(i - fruits[items[i]][:weight], items, minWeight)
else
[]
end
}
solution.call(limit, iterate.call(fruits.size - 1)[:items],
fruits.map { |fruit| fruit[:weight] }.min)
end
def fruit(n, w, p)
{name: n, weight: w, price: p}
end
knapsack([fruit('李子', 4, 4500), fruit('蘋果', 5, 5700),
fruit('橘子', 2, 2250), fruit('草莓', 1, 1100),
fruit('甜瓜', 6, 6700)], 8).each do |fruit|
print "(#{fruit[:name]}, #{fruit[:weight]}, #{fruit[:price]})"
end
function fruit(n, w, p) {
return { name : n, weight : w, price : p };
}
function knapsack(fruits, limit) {
Array.prototype.reduce = function(init, f) {
var value = init;
for(var i = 0; i < this.length; i++) {
value = f(value, this[i]);
}
return value;
};
function range(n) {
var list = [];
for(var i = 0; i < n; i++) {
list[i] = i;
}
return list;
}
function nextVI(i, values, items) {
return range(values.length).map(function(w) {
return w >= fruits[i].weight && w < limit + 1 &&
values[w - fruits[i].weight] + fruits[i].price > values[w] ?
{
value : values[w - fruits[i].weight] + fruits[i].price,
item : i
} :
{value : values[w], item : items[w]};
}).reduce({values : [], items : []}, function(vis, vi) {
return { values : vis.values.concat([vi.value]),
items : vis.items.concat([vi.item])
};
});
}
function iterate(i) {
if(i == 0) {
return nextVI(i,
range(limit + 1).map(function(elem) { return 0; }),
range(limit + 1).map(function(elem) { return 0; }));
} else {
var vis = iterate(i - 1)
return nextVI(i, vis.values, vis.items);
}
}
function solution(i, items, minWeight) {
if(i >= minWeight) {
return [fruits[items[i]]].concat(
solution(i - fruits[items[i]].weight, items, minWeight));
} else {
return [];
}
}
return solution(limit, iterate(fruits.length - 1).items,
fruits.reduce(fruits[0].weight, function(seed, elem) {
return elem < seed ? elem : seed;
})
);
}
knapsack([fruit('李子', 4, 4500), fruit('蘋果', 5, 5700),
fruit('橘子', 2, 2250), fruit('草莓', 1, 1100),
fruit('甜瓜', 6, 6700)], 8).forEach(function(fruit) {
print(fruit.name);
});
data Fruit = Fruit { name :: String,
weight :: Int,
price ::Int } deriving (Show)
knapsack fruits limit =
solution limit (snd $ iterate $ length fruits - 1)
(minimum $ map (\f -> weight f) fruits)
where nextVI i values items =
let viList = [if w >= weight (fruits !! i) && w < limit + 1 &&
values !! (w - weight (fruits !! i)) + price (fruits !! i)
> values !! w
then (values !! (w - weight (fruits !! i)) +
price (fruits !! i), i)
else (values !! w, items !! w) |
w <- [0 .. length values - 1]]
in foldr (\vi vis -> (fst vi : fst vis, snd vi : snd vis))
([], []) viList
iterate i =
if i == 0 then
nextVI i [0 | i <- [0..8]] [0 | i <- [0..8]]
else
let (values, items) = iterate $ i - 1
in nextVI i values items
solution i items minWeight =
if i >= minWeight then
fruits !! (items !! i) :
solution (i - weight (fruits !! (items !! i)))
items minWeight
else []
main = print $ knapsack [
Fruit "Plum" 4 4500, Fruit "Apple" 5 5700,
Fruit "Tangerine" 2 2250, Fruit "Strawberry" 1 1100,
Fruit "Sweet melon" 6 6700] 8