背包問題(Knapsack Problem)


說明

假設有一個背包的負重最多可達8公斤,而希望在背包中裝入負重範圍內可得之總價物品,假設是水果好了,水果的編號、單價與重量如下所示:
0 李子 4KG NT$4500
1 蘋果 5KG NT$5700
2 橘子 2KG NT$2250
3 草莓 1KG NT$1100
4 甜瓜 6KG NT$6700

解法

背包問題是關於最佳化的問題,要解最佳化問題可以使用「動態規劃」(Dynamic programming),從空集合開始,每增加一個元素就先求出該階段的最佳解,直到所有的元素加入至集合中,最後得到的就是最佳解。

以背包問題為例,我們使用兩個陣列value與item,value表示目前的最佳解所得之總價,item表示最後一個放至背包的水果,假設有負重量 1~8的背包8個,並對每個背包求其最佳解。

逐步將水果放入背包中,並求該階段的最佳解:
  • 放入李子
背包負重 1 2 3 4 5 6 7 8
value 4500 4500 4500 4500 9000
item

  • 放入蘋果
背包負重 1 2 3 4 5 6 7 8
value 4500 5700 5700 5700 9000
item 1 1 1
  • 放入橘子
背包負重 1 2 3 4 5 6 7 8
value 2250 2250 4500 5700 6750 7950 9000
item 2 2 1 2 2

  • 放入草莓
背包負重 1 2 3 4 5 6 7 8
value 1100 2250 3350 4500 5700 6800 7950 9050
item 3 2 3 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 1 3 2 3

由最後一個表格,可以得知在背包負重8公斤時,最多可以裝入9050元的水果,而最後一個裝入的 水果是3號,也就是草莓,裝入了草莓,背包只能再放入7公斤(8-1)的水果,所以必須看背包負重7公斤時的最佳解,最後一個放入的是2號,也就 是橘子,現在背包剩下負重量5公斤(7-2),所以看負重5公斤的最佳解,最後放入的是1號,也就是蘋果,此時背包負重量剩下0公斤(5-5),無法 再放入水果,所以求出最佳解為放入草莓、橘子與蘋果,而總價為9050元。

實作:C    Java    Python    Scala    Ruby    JavaScript    Haskell

  • C
#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;
}

  • Java
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));
}
}

  • Python
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))

  • Scala
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))

  • Ruby
# 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

  • JavaScript
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);
});

  • Haskell
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