# 背包問題（Knapsack Problem）

## 說明

 0 李子 4KG NT\$4500 1 蘋果 5KG NT\$5700 2 橘子 2KG NT\$2250 3 草莓 1KG NT\$1100 4 甜瓜 6KG NT\$6700

## 解法

 背包負重 1 2 3 4 5 6 7 8 value 0 0 0 4500 4500 4500 4500 9000 item － － － 0 0 0 0 0

 背包負重 1 2 3 4 5 6 7 8 value 0 0 0 4500 5700 5700 5700 9000 item － － － 0 1 1 1 0

 背包負重 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

``````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 reducedef 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))``

``# encoding: Big5def 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)enddef fruit(n, w, p)    {name: n, weight: w, price: p}endknapsack([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``