# 背包問題

December 1, 2021

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

## 解法思路

### 一種水果

1 0 -
2 0 -
3 0 -
4 4500 0
5 4500 0
6 4500 0
7 4500 0
8 9000 0

8 公斤時可以放入一個李子，價值為 4500 元，還可以負擔 4 公斤，對應的價值為 4500 元，4500 + 4500 的總價大於目前對應的 value 值，於是更新…

1 0 -
2 0 -
3 0 -
4 4500 0
5 5700 1
6 5700 1
7 5700 1
8 9000 0

1 0 -
2 2250 2
3 2250 2
4 4500 0
5 5700 1
6 6750 2
7 7950 2
8 9000 0

1 1100 3
2 2250 2
3 3350 3
4 4500 0
5 5700 1
6 6800 3
7 7950 2
8 9050 3

1 1100 3
2 2250 2
3 3350 3
4 4500 0
5 5700 1
6 6800 3
7 7950 2
8 9050 3

## 程式實作

``````#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) {
}
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)))
``````