背包問題（Knapsack Problem）

說明

解法

• 放入李子

• 放入蘋果

• 放入橘子

• 放入草莓

• 放入甜瓜

實作：Toy    C    Java    Python    Scala    Ruby    JavaScript    Haskell

• Toy

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

• 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