背包問題

December 1, 2021

假設背包負重最多可達 8 公斤,希望在背包中裝入的物品,在負重範圍內可得最高總價,假設是水果好了,水果的編號、單價與重量如下所示:

編號 種類 重量 價格
0 李子 4KG 4500
1 蘋果 5KG 5700
2 橘子 2KG 2250
3 草莓 1KG 1100
4 甜瓜 6KG 6700

解法思路

背包問題是關於最佳化的問題,可以使用動態規劃(Dynamic programming),試著解決構成的大問題之小問題,基於小問題的最佳解答來解決大問題,最後得到的就是大問題的最佳解。

以背包問題為例,要解決背包負重為 8 公斤,水果有 5 個的問題,可以先解決背包負重為 1 公斤,水果有 1 個的問題,接著解決背包負重為 2 公斤,水果有 1 個的問題,然後解決背包負重為 3 公斤,水果有 1 個的問題…

一種水果

若使用兩個陣列 value 與 item,value 表示目前負重下可得的最大總價,一開始都是 0,item 表示最後放至背包的水果,首先是只有李子,從可以負重 1 公斤到可以負重 8 公斤,能得到的最大總價各是:

背包負重 value item
1 0 -
2 0 -
3 0 -
4 4500 0
5 4500 0
6 4500 0
7 4500 0
8 9000 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,於是不更新。

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

因此在可以負重 8 公斤,只有李子、蘋果的情況下,可以得到的最大總價是 9000 元,最後放入的李子是 4 公斤,裝入這顆李子前,背包能負重的是 4 公斤的水果,4 公斤處對應的水果是李子,因此目前最佳解為 9000 元,兩顆李子。

更多種水果

接著處理背包負重為 1 公斤,可能的水果有 3 個的問題,背包負重為 2 公斤,可能的水果有 3 個的問題,背包負重為3公斤,可能的水果有 3 個的問題…因為方才已經處理過只有李子、蘋果的運算,現在可以基於其結果,直接考慮該如何置入橘子,依方才的演算方式,可以得到:

背包負重 value item
1 0 -
2 2250 2
3 2250 2
4 4500 0
5 5700 1
6 6750 2
7 7950 2
8 9000 0

接著基於以上,處理加上草莓的情況:

背包負重 value item
1 1100 3
2 2250 2
3 3350 3
4 4500 0
5 5700 1
6 6800 3
7 7950 2
8 9050 3

接著基於以上,處理加上甜瓜的情況:

背包負重 value item
1 1100 3
2 2250 2
3 3350 3
4 4500 0
5 5700 1
6 6800 3
7 7950 2
8 9050 3

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

程式實作

#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: UTF-8
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
# 我寫的玩具語言 https://github.com/JustinSDK/toy_lang

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