From Gossip@caterpillar

Algorithm Gossip: 背包問題（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

#include <stdio.h> 
#include <stdlib.h> 

#define LIMIT 8   // 重量限制 
#define N 5       // 物品種類 
#define MIN 1     // 最小重量 

struct body { 
    char name[20]; 
    int size; 
    int price; 
}; 

typedef struct body object; 

int main(void) { 
    int item[LIMIT+1] = {0}; 
    int value[LIMIT+1] = {0}; 

    object a[] = {{"李子", 4, 4500}, 
                  {"蘋果", 5, 5700}, 
                  {"橘子", 2, 2250}, 
                  {"草莓", 1, 1100}, 
                  {"甜瓜", 6, 6700}}; 

    int i, s;
    for(i = 0; i < N; i++) { 
        for(s = a[i].size; s <= LIMIT; s++) { 
            int p = s - a[i].size; 
            int newvalue = value[p] + a[i].price; 
            if(newvalue > value[s]) {// 找到階段最佳解 
                value[s] = newvalue; 
                item[s] = i; 
            } 
        } 
    } 

    printf("物品\t價格\n"); 
    for(i = LIMIT; i >= MIN; i = i - a[item[i]].size) { 
        printf("%s\t%d\n", 
                  a[item[i]].name, a[item[i]].price); 
    } 

    printf("合計\t%d\n", value[LIMIT]); 

    return 0; 
}

Java

class Fruit {
    public final String name;
    public final int size;
    public final int price;
    
    public Fruit(String name, int size, int price) {
        this.name = name;
        this.size = size;
        this.price = price;
    }
}

public class Knapsack {
    public static void main(String[] args) {
        final int MAX = 8;
        final int MIN = 1;
        int[] item = new int[MAX+1]; 
        int[] value = new int[MAX+1];  

        Fruit fruits[] = {
                new Fruit("李子", 4, 4500), 
                new Fruit("蘋果", 5, 5700), 
                new Fruit("橘子", 2, 2250), 
                new Fruit("草莓", 1, 1100), 
                new Fruit("甜瓜", 6, 6700)}; 

        for(int i = 0; i < fruits.length; i++) { 
            for(int s = fruits[i].size; s <= MAX; s++) { 
                int p = s - fruits[i].size; 
                int newValue = value[p] + fruits[i].price; 
                if(newValue > value[s]) {// 找到階段最佳解 
                    value[s] = newValue; 
                    item[s] = i; 
                } 
            } 
        } 

        System.out.println("物品\t價格"); 
        for(int i = MAX; i >= MIN; i -= fruits[item[i]].size) { 
            System.out.println(fruits[item[i]].name+ 
                    "\t" + fruits[item[i]].price); 
        } 

        System.out.println("合計\t" + value[MAX]);  
    }
}

Python

class Fruit:
    def __init__(self, name, size, price):
        self.name = name
        self.size = size
        self.price = price

MAX = 8
MIN = 1
item = [0] * (MAX + 1)
value = [0] * (MAX + 1)

fruits = [
            Fruit("李子", 4, 4500), 
            Fruit("蘋果", 5, 5700), 
            Fruit("橘子", 2, 2250), 
            Fruit("草莓", 1, 1100), 
            Fruit("甜瓜", 6, 6700)
         ]
   
for i in range(len(fruits)):
    for s in range(fruits[i].size, MAX + 1):
        p = s - fruits[i].size
        newValue = value[p] + fruits[i].price
        if newValue > value[s]:
            value[s] = newValue
            item[s] = i

print("物品\t價格")
i = MAX
while(i >= MIN):
    print(fruits[item[i]].name, "\t", fruits[item[i]].price)
    i -= fruits[item[i]].size
print("合計\t", value[MAX])

Scala

case class Fruit(name: String, size: Int, price: Int)

val MAX = 8
val MIN = 1
val item = new Array[Int](MAX + 1)
val value = new Array[Int](MAX + 1)
val fruits = Array(
                Fruit("李子", 4, 4500),
                Fruit("蘋果", 5, 5700),
                Fruit("橘子", 2, 2250),
                Fruit("草莓", 1, 1100),
                Fruit("甜瓜", 6, 6700)
            );
for(
  i <- 0 until fruits.length; s <- fruits(i).size to MAX;
  p = s - fruits(i).size; newValue = value(p) + fruits(i).price 
  if newValue > value(s)) {
    value(s) = newValue
    item(s) = i
}
println("物品\t價格")
var i = MAX
while(i >= MIN) {
    printf("%s\t%d%n", fruits(item(i)).name, fruits(item(i)).price)
    i -= fruits(item(i)).size
}
printf("合計\t%d%n", value(MAX))

Ruby

# encoding: Big5
class Fruit
    attr_accessor :name
    attr_accessor :size
    attr_accessor :price
    def initialize(name, size, price)
        @name = name
        @size = size
        @price = price
    end
end

MAX = 8
MIN = 1
item = Array.new(MAX + 1, 0)
value = Array.new(MAX + 1, 0)

fruits = [
    Fruit.new("李子", 4, 4500),
    Fruit.new("蘋果", 5, 5700),
    Fruit.new("橘子", 2, 2250),
    Fruit.new("草莓", 1, 1100),
    Fruit.new("甜瓜", 6, 6700)
]

fruits.length.times { |i|
    fruits[i].size.upto(MAX) { |s|
        p = s - fruits[i].size
        newValue = value[p] + fruits[i].price
        if newValue > value[s]
            value[s] = newValue
            item[s] = i
        end
    }
}

puts "物品\t價格"
i = MAX
while i >= MIN
    printf("%s\t%d\n", 
        fruits[item[i]].name, fruits[item[i]].price)
    i -= fruits[item[i]].size
end
printf("合計\t%d\n", value[MAX])