Knapsack problem/Bounded
You are encouraged to solve this task according to the task description, using any language you may know.
A tourist wants to make a good trip at the weekend with his friends.
They will go to the mountains to see the wonders of nature. So he needs some items during the trip. Food, clothing, etc. He has a good knapsack for carrying the things, but he knows that he can carry only 4 kg weight in his knapsack, because they will make the trip from morning to evening.
He creates a list of what he wants to bring for the trip, but the total weight of all items is too much. He adds a value to each item. The value represents how important the thing for the tourist.
The list contains which items are the wanted things for the trip, what is the weight and value of an item, and how many units does he have from each items.
This is the list:
Table of potential knapsack items item weight (dag) (each) value (each) piece(s) map 9 150 1 compass 13 35 1 water 153 200 2 sandwich 50 60 2 glucose 15 60 2 tin 68 45 3 banana 27 60 3 apple 39 40 3 cheese 23 30 1 beer 52 10 3 suntan cream 11 70 1 camera 32 30 1 T-shirt 24 15 2 trousers 48 10 2 umbrella 73 40 1 waterproof trousers 42 70 1 waterproof overclothes 43 75 1 note-case 22 80 1 sunglasses 7 20 1 towel 18 12 2 socks 4 50 1 book 30 10 2 knapsack ≤400 dag ? ?
The tourist can choose to take any combination of items from the list, and some number of each item is available (see the column piece(s) in the list above).
He may not cut the items, so he can only take whole units of any item.
- Task
Show which items does the tourist carry in his knapsack so that their total weight does not exceed 4 kg, and their total value is maximized.
- Related tasks
11l
V items = [
‘sandwich’ = (50, 60, 2),
‘map’ = (9, 150, 1),
‘compass’ = (13, 35, 1),
‘water’ = (153, 200, 3),
‘glucose’ = (15, 60, 2),
‘tin’ = (68, 45, 3),
‘banana’ = (27, 60, 3),
‘apple’ = (39, 40, 3),
‘cheese’ = (23, 30, 1),
‘beer’ = (52, 10, 3),
‘suntan cream’ = (11, 70, 1),
‘camera’ = (32, 30, 1),
‘t-shirt’ = (24, 15, 2),
‘trousers’ = (48, 10, 2),
‘umbrella’ = (73, 40, 1),
‘w-trousers’ = (42, 70, 1),
‘w-overcoat’ = (43, 75, 1),
‘note-case’ = (22, 80, 1),
‘sunglasses’ = (7, 20, 1),
‘towel’ = (18, 12, 2),
‘socks’ = (4, 50, 1),
‘book’ = (30, 10, 2)
]
V item_keys = items.keys()
[(Int, Int) = (Int, [(Int, String)])] cache
F choose_item(weight, idx)
[(Int, String)] best_list
I idx < 0
R (0, best_list)
V k = (weight, idx)
V? c = :cache.find(k)
I c != N
R c
V name = :item_keys[idx]
V (w, v, qty) = :items[name]
V best_v = 0
L(i) 0..qty
V wlim = weight - i * w
I wlim < 0
L.break
V (val, taken) = choose_item(wlim, idx - 1)
I val + i * v > best_v
best_v = val + i * v
best_list = copy(taken)
best_list.append((i, name))
:cache[k] = (best_v, best_list)
R (best_v, best_list)
V (v, lst) = choose_item(400, items.len - 1)
V w = 0
L(cnt, name) lst
I cnt > 0
print(cnt‘ ’name)
w += items[name][0] * cnt
print(‘Total weight: ’w‘ Value: ’v)- Output:
3 banana 1 cheese 1 compass 2 glucose 1 map 1 note-case 1 socks 1 sunglasses 1 suntan cream 1 w-overcoat 1 water Total weight: 396 Value: 1010
AutoHotkey
iterative dynamic programming solution
Item = map,compass,water,sandwich,glucose,tin,banana,apple,cheese,beer,suntan cream
,camera,tshirt,trousers,umbrella,waterproof trousers,waterproof overclothes,notecase
,sunglasses,towel,socks,book
Weight= 9,13,153,50,15,68,27,39,23,52,11,32,24,48,73,42,43,22,7,18,4,30
Value = 150,35,200,60,60,45,60,40,30,10,70,30,15,10,40,70,75,80,20,12,50,10
Bound = 1,1,2,2,2,3,3,3,1,3,1,1,2,2,1,1,1,1,1,2,1,2
StringSplit I, Item, `, ; Put input in arrays
StringSplit W, Weight,`,
StringSplit V, Value, `,
StringSplit B, Bound, `,
W := 400, N := I0, I0 := V0 := W0 := 0 ; W = total weight allowed, maximize total value
Loop %W%
m0_%A_Index% := 0
Loop %N% { ; build achievable value matrix m [ N rows, W columns ]
j := -1+i := A_Index, m%j%_0 := 0 ; m[i,P] = max value with items 1..i, weight <=P
Loop %W% { ; m[i,P] = max_k {m[i-1,P-k*Wi]}
p := A_Index, k := 0, y := m%j%_%p%
While ++k <= B%i% && (r := p - k*W%i%) >= 0
y := y < (c:=m%j%_%r%+k*V%i%) ? c : y
m%i%_%p% := y
}
}
i := 1+j := N, p := W, s := 0
While --i, --j { ; read out solution from value matrix m
If (m%i%_%p% = m%j%_%p%)
Continue
r := p, m := m%i%_%p%, k := 1
While 0 <= (r-=W%i%) && m%j%_%r% != (m-=V%i%)
k++ ; find multiplier
t := k " " I%i% "`n" t, s += k*W%i%, p -= k*W%i%
}
MsgBox % "Value = " m%N%_%W% "`nWeight = " s "`n`n" t
Bracmat
(knapsack=
( things
= (map.9.150.1)
(compass.13.35.1)
(water.153.200.2)
(sandwich.50.60.2)
(glucose.15.60.2)
(tin.68.45.3)
(banana.27.60.3)
(apple.39.40.3)
(cheese.23.30.1)
(beer.52.10.3)
(suntan cream.11.70.1)
(camera.32.30.1)
(T-shirt.24.15.2)
(trousers.48.10.2)
(umbrella.73.40.1)
(waterproof trousers.42.70.1)
(waterproof overclothes.43.75.1)
(note-case.22.80.1)
(sunglasses.7.20.1)
(towel.18.12.2)
(socks.4.50.1)
(book.30.10.2)
)
& 0:?maxvalue
& :?sack
& ( add
= cumwght
cumvalue
cumsack
name
wght
val
pcs
tings
n
ncumwght
ncumvalue
. !arg
: ( ?cumwght
. ?cumvalue
. ?cumsack
. (?name.?wght.?val.?pcs) ?tings
)
& -1:?n
& whl
' ( 1+!n:~>!pcs:?n
& !cumwght+!n*!wght:~>400:?ncumwght
& !cumvalue+!n*!val:?ncumvalue
& ( !tings:
& ( !ncumvalue:>!maxvalue:?maxvalue
& !cumsack
( !n:0&
| (!n.!name)
)
: ?sack
|
)
| add
$ ( !ncumwght
. !ncumvalue
. !cumsack
(!n:0&|(!n.!name))
. !tings
)
)
)
)
& add$(0.0..!things)
& out$(!maxvalue.!sack)
);
!knapsack;- Output:
1010
. (1.map)
(1.compass)
(1.water)
(2.glucose)
(3.banana)
(1.cheese)
(1.suntan cream)
(1.waterproof overclothes)
(1.note-case)
(1.sunglasses)
(1.socks)
C
#include <stdio.h>
#include <stdlib.h>
typedef struct {
char *name;
int weight;
int value;
int count;
} item_t;
item_t items[] = {
{"map", 9, 150, 1},
{"compass", 13, 35, 1},
{"water", 153, 200, 2},
{"sandwich", 50, 60, 2},
{"glucose", 15, 60, 2},
{"tin", 68, 45, 3},
{"banana", 27, 60, 3},
{"apple", 39, 40, 3},
{"cheese", 23, 30, 1},
{"beer", 52, 10, 3},
{"suntan cream", 11, 70, 1},
{"camera", 32, 30, 1},
{"T-shirt", 24, 15, 2},
{"trousers", 48, 10, 2},
{"umbrella", 73, 40, 1},
{"waterproof trousers", 42, 70, 1},
{"waterproof overclothes", 43, 75, 1},
{"note-case", 22, 80, 1},
{"sunglasses", 7, 20, 1},
{"towel", 18, 12, 2},
{"socks", 4, 50, 1},
{"book", 30, 10, 2},
};
int n = sizeof (items) / sizeof (item_t);
int *knapsack (int w) {
int i, j, k, v, *mm, **m, *s;
mm = calloc((n + 1) * (w + 1), sizeof (int));
m = malloc((n + 1) * sizeof (int *));
m[0] = mm;
for (i = 1; i <= n; i++) {
m[i] = &mm[i * (w + 1)];
for (j = 0; j <= w; j++) {
m[i][j] = m[i - 1][j];
for (k = 1; k <= items[i - 1].count; k++) {
if (k * items[i - 1].weight > j) {
break;
}
v = m[i - 1][j - k * items[i - 1].weight] + k * items[i - 1].value;
if (v > m[i][j]) {
m[i][j] = v;
}
}
}
}
s = calloc(n, sizeof (int));
for (i = n, j = w; i > 0; i--) {
int v = m[i][j];
for (k = 0; v != m[i - 1][j] + k * items[i - 1].value; k++) {
s[i - 1]++;
j -= items[i - 1].weight;
}
}
free(mm);
free(m);
return s;
}
int main () {
int i, tc = 0, tw = 0, tv = 0, *s;
s = knapsack(400);
for (i = 0; i < n; i++) {
if (s[i]) {
printf("%-22s %5d %5d %5d\n", items[i].name, s[i], s[i] * items[i].weight, s[i] * items[i].value);
tc += s[i];
tw += s[i] * items[i].weight;
tv += s[i] * items[i].value;
}
}
printf("%-22s %5d %5d %5d\n", "count, weight, value:", tc, tw, tv);
return 0;
}
- Output:
map 1 9 150 compass 1 13 35 water 1 153 200 glucose 2 30 120 banana 3 81 180 cheese 1 23 30 suntan cream 1 11 70 waterproof overclothes 1 43 75 note-case 1 22 80 sunglasses 1 7 20 socks 1 4 50 count, weight, value: 14 396 1010
C#
Similar to Knapsack/0-1.
using System; // 4790@3.6
class program
{
static void Main()
{
knapSack(40);
var sw = System.Diagnostics.Stopwatch.StartNew();
Console.Write(knapSack(400) + "\n" + sw.Elapsed); // 51 µs
Console.Read();
}
static string knapSack(uint w1)
{
init(); change();
uint n = (uint)w.Length; var K = new uint[n + 1, w1 + 1];
for (uint vi, wi, w0, x, i = 0; i < n; i++)
for (vi = v[i], wi = w[i], w0 = 1; w0 <= w1; w0++)
{
x = K[i, w0];
if (wi <= w0) x = max(vi + K[i, w0 - wi], x);
K[i + 1, w0] = x;
}
string str = "";
for (uint v1 = K[n, w1]; v1 > 0; n--)
if (v1 != K[n - 1, w1])
{
v1 -= v[n - 1]; w1 -= w[n - 1]; str += items[n - 1] + "\n";
}
return str;
}
static uint max(uint a, uint b) { return a > b ? a : b; }
static byte[] w, v; static string[] items;
static byte[] p = { 1, 1, 2, 2, 2, 3, 3, 3, 1, 3, 1, 1, 2, 2, 1, 1, 1, 1, 1, 2, 1, 2 };
static void init()
{
w = new byte[] { 9, 13, 153, 50, 15, 68, 27, 39, 23, 52, 11,
32, 24, 48, 73, 42, 43, 22, 7, 18, 4, 30 };
v = new byte[] { 150, 35, 200, 60, 60, 45, 60, 40, 30, 10, 70,
30, 15, 10, 40, 70, 75, 80, 20, 12, 50, 10 };
items = new string[] {"map","compass","water","sandwich","glucose","tin",
"banana","apple","cheese","beer","suntan cream",
"camera","T-shirt","trousers","umbrella",
"waterproof trousers","waterproof overclothes",
"note-case","sunglasses","towel","socks","book"};
}
static void change()
{
int n = w.Length, s = 0, i, j, k; byte xi;
for (i = 0; i < n; i++) s += p[i];
{
byte[] x = new byte[s];
for (k = i = 0; i < n; i++)
for (xi = w[i], j = p[i]; j > 0; j--) x[k++] = xi;
w = x;
}
{
byte[] x = new byte[s];
for (k = i = 0; i < n; i++)
for (xi = v[i], j = p[i]; j > 0; j--) x[k++] = xi;
v = x;
}
string[] pItems = new string[s]; string itemI;
for (k = i = 0; i < n; i++)
for (itemI = items[i], j = p[i]; j > 0; j--) pItems[k++] = itemI;
items = pItems;
}
}
C++
C++ DP solution. Initially taken from C but than fixed and refactored.
Remark: The above comment implies there is a bug in the C code, but refers to a much older and very different version Pete Lomax (talk) 19:28, 20 March 2017 (UTC)
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdexcept>
#include <memory>
#include <sys/time.h>
using std::cout;
using std::endl;
class StopTimer
{
public:
StopTimer(): begin_(getUsec()) {}
unsigned long long getTime() const { return getUsec() - begin_; }
private:
static unsigned long long getUsec()
{//...you might want to use something else under Windows
timeval tv;
const int res = ::gettimeofday(&tv, 0);
if(res)
return 0;
return tv.tv_usec + 1000000 * tv.tv_sec;
}
unsigned long long begin_;
};
struct KnapsackTask
{
struct Item
{
std::string name;
unsigned w, v, qty;
Item(): w(), v(), qty() {}
Item(const std::string& iname, unsigned iw, unsigned iv, unsigned iqty):
name(iname), w(iw), v(iv), qty(iqty)
{}
};
typedef std::vector<Item> Items;
struct Solution
{
unsigned v, w;
unsigned long long iterations, usec;
std::vector<unsigned> n;
Solution(): v(), w(), iterations(), usec() {}
};
//...
KnapsackTask(): maxWeight_(), totalWeight_() {}
void add(const Item& item)
{
const unsigned totalItemWeight = item.w * item.qty;
if(const bool invalidItem = !totalItemWeight)
throw std::logic_error("Invalid item: " + item.name);
totalWeight_ += totalItemWeight;
items_.push_back(item);
}
const Items& getItems() const { return items_; }
void setMaxWeight(unsigned maxWeight) { maxWeight_ = maxWeight; }
unsigned getMaxWeight() const { return std::min(totalWeight_, maxWeight_); }
private:
unsigned maxWeight_, totalWeight_;
Items items_;
};
class BoundedKnapsackRecursiveSolver
{
public:
typedef KnapsackTask Task;
typedef Task::Item Item;
typedef Task::Items Items;
typedef Task::Solution Solution;
void solve(const Task& task)
{
Impl(task, solution_).solve();
}
const Solution& getSolution() const { return solution_; }
private:
class Impl
{
struct Candidate
{
unsigned v, n;
bool visited;
Candidate(): v(), n(), visited(false) {}
};
typedef std::vector<Candidate> Cache;
public:
Impl(const Task& task, Solution& solution):
items_(task.getItems()),
maxWeight_(task.getMaxWeight()),
maxColumnIndex_(task.getItems().size() - 1),
solution_(solution),
cache_(task.getMaxWeight() * task.getItems().size()),
iterations_(0)
{}
void solve()
{
if(const bool nothingToSolve = !maxWeight_ || items_.empty())
return;
StopTimer timer;
Candidate candidate;
solve(candidate, maxWeight_, items_.size() - 1);
convertToSolution(candidate);
solution_.usec = timer.getTime();
}
private:
void solve(Candidate& current, unsigned reminderWeight, const unsigned itemIndex)
{
++iterations_;
const Item& item(items_[itemIndex]);
if(const bool firstColumn = !itemIndex)
{
const unsigned maxQty = std::min(item.qty, reminderWeight/item.w);
current.v = item.v * maxQty;
current.n = maxQty;
current.visited = true;
}
else
{
const unsigned nextItemIndex = itemIndex - 1;
{
Candidate& nextItem = cachedItem(reminderWeight, nextItemIndex);
if(!nextItem.visited)
solve(nextItem, reminderWeight, nextItemIndex);
current.visited = true;
current.v = nextItem.v;
current.n = 0;
}
if(reminderWeight >= item.w)
{
for (unsigned numberOfItems = 1; numberOfItems <= item.qty; ++numberOfItems)
{
reminderWeight -= item.w;
Candidate& nextItem = cachedItem(reminderWeight, nextItemIndex);
if(!nextItem.visited)
solve(nextItem, reminderWeight, nextItemIndex);
const unsigned checkValue = nextItem.v + numberOfItems * item.v;
if ( checkValue > current.v)
{
current.v = checkValue;
current.n = numberOfItems;
}
if(!(reminderWeight >= item.w))
break;
}
}
}
}
void convertToSolution(const Candidate& candidate)
{
solution_.iterations = iterations_;
solution_.v = candidate.v;
solution_.n.resize(items_.size());
const Candidate* iter = &candidate;
unsigned weight = maxWeight_, itemIndex = items_.size() - 1;
while(true)
{
const unsigned currentWeight = iter->n * items_[itemIndex].w;
solution_.n[itemIndex] = iter->n;
weight -= currentWeight;
if(!itemIndex--)
break;
iter = &cachedItem(weight, itemIndex);
}
solution_.w = maxWeight_ - weight;
}
Candidate& cachedItem(unsigned weight, unsigned itemIndex)
{
return cache_[weight * maxColumnIndex_ + itemIndex];
}
const Items& items_;
const unsigned maxWeight_;
const unsigned maxColumnIndex_;
Solution& solution_;
Cache cache_;
unsigned long long iterations_;
};
Solution solution_;
};
void populateDataset(KnapsackTask& task)
{
typedef KnapsackTask::Item Item;
task.setMaxWeight( 400 );
task.add(Item("map",9,150,1));
task.add(Item("compass",13,35,1));
task.add(Item("water",153,200,2));
task.add(Item("sandwich",50,60,2));
task.add(Item("glucose",15,60,2));
task.add(Item("tin",68,45,3));
task.add(Item("banana",27,60,3));
task.add(Item("apple",39,40,3));
task.add(Item("cheese",23,30,1));
task.add(Item("beer",52,10,3));
task.add(Item("suntancream",11,70,1));
task.add(Item("camera",32,30,1));
task.add(Item("T-shirt",24,15,2));
task.add(Item("trousers",48,10,2));
task.add(Item("umbrella",73,40,1));
task.add(Item("w-trousers",42,70,1));
task.add(Item("w-overclothes",43,75,1));
task.add(Item("note-case",22,80,1));
task.add(Item("sunglasses",7,20,1));
task.add(Item("towel",18,12,2));
task.add(Item("socks",4,50,1));
task.add(Item("book",30,10,2));
}
int main()
{
KnapsackTask task;
populateDataset(task);
BoundedKnapsackRecursiveSolver solver;
solver.solve(task);
const KnapsackTask::Solution& solution = solver.getSolution();
cout << "Iterations to solve: " << solution.iterations << endl;
cout << "Time to solve: " << solution.usec << " usec" << endl;
cout << "Solution:" << endl;
for (unsigned i = 0; i < solution.n.size(); ++i)
{
if (const bool itemIsNotInKnapsack = !solution.n[i])
continue;
cout << " " << solution.n[i] << ' ' << task.getItems()[i].name << " ( item weight = " << task.getItems()[i].w << " )" << endl;
}
cout << "Weight: " << solution.w << " Value: " << solution.v << endl;
return 0;
}
Clojure
We convert the problem to a Knapsack-0/1 problem by replacing (n-max item) vith n-max identical occurences of 1 item. Adapted Knapsack-0/1 problem solution from [1]
(ns knapsack
(:gen-class))
(def groupeditems [
["map", 9, 150, 1]
["compass", 13, 35, 1]
["water", 153, 200, 3]
["sandwich", 50, 60, 2]
["glucose", 15, 60, 2]
["tin", 68, 45, 3]
["banana", 27, 60, 3]
["apple", 39, 40, 3]
["cheese", 23, 30, 1]
["beer", 52, 10, 3]
["suntan cream", 11, 70, 1]
["camera", 32, 30, 1]
["t-shirt", 24, 15, 2]
["trousers", 48, 10, 2]
["umbrella", 73, 40, 1]
["waterproof trousers", 42, 70, 1]
["waterproof overclothes", 43, 75, 1]
["note-case", 22, 80, 1]
["sunglasses", 7, 20, 1]
["towel", 18, 12, 2]
["socks", 4, 50, 1]
["book", 30, 10, 2]
])
(defstruct item :name :weight :value)
(def items (->> (for [[item wt val n] groupeditems]
(repeat n [item wt val]))
(mapcat identity)
(map #(apply struct item %))
(vec)))
(declare mm) ;forward decl for memoization function
(defn m [i w]
(cond
(< i 0) [0 []]
(= w 0) [0 []]
:else
(let [{wi :weight vi :value} (get items i)]
(if (> wi w)
(mm (dec i) w)
(let [[vn sn :as no] (mm (dec i) w)
[vy sy :as yes] (mm (dec i) (- w wi))]
(if (> (+ vy vi) vn)
[(+ vy vi) (conj sy i)]
no))))))
(def mm (memoize m))
(let [[value indexes] (mm (-> items count dec) 400)
names (map (comp :name items) indexes)]
(println "Items to pack:")
(doseq [[k v] (frequencies names)]
(println (format "%d %s" v k)))
(println "Total value:" value)
(println "Total weight:" (reduce + (map (comp :weight items) indexes))))
- Output:
Items to pack: 1 suntan cream 1 map 3 banana 1 water 1 compass 2 glucose 1 note-case 1 waterproof overclothes 1 cheese 1 sunglasses 1 socks Total value: 1010 Total weight: 396
Common Lisp
;;; memoize
(defmacro mm-set (p v) `(if ,p ,p (setf ,p ,v)))
(defun knapsack (max-weight items)
(let ((cache (make-array (list (1+ max-weight) (1+ (length items)))
:initial-element nil)))
(labels ((knapsack1 (spc items)
(if (not items) (return-from knapsack1 (list 0 0 '())))
(mm-set (aref cache spc (length items))
(let* ((i (first items))
(w (second i))
(v (third i))
(x (knapsack1 spc (cdr items))))
(loop for cnt from 1 to (fourth i) do
(let ((w (* cnt w)) (v (* cnt v)))
(if (>= spc w)
(let ((y (knapsack1 (- spc w) (cdr items))))
(if (> (+ (first y) v) (first x))
(setf x (list (+ (first y) v)
(+ (second y) w)
(cons (list (first i) cnt) (third y)))))))))
x))))
(knapsack1 max-weight items))))
(print
(knapsack 400
'((map 9 150 1) (compass 13 35 1) (water 153 200 2) (sandwich 50 60 2)
(glucose 15 60 2) (tin 68 45 3) (banana 27 60 3) (apple 39 40 3)
(cheese 23 30 1) (beer 52 10 3) (cream 11 70 1) (camera 32 30 1)
(T-shirt 24 15 2) (trousers 48 10 2) (umbrella 73 40 1)
(trousers 42 70 1) (overclothes 43 75 1) (notecase 22 80 1)
(glasses 7 20 1) (towel 18 12 2) (socks 4 50 1) (book 30 10 2))))
Crystal
Branch and Bound solution
record Item, name : String, weight : Int32, value : Int32, count : Int32
record Selection, mask : Array(Int32), cur_index : Int32, total_value : Int32
class Knapsack
@threshold_value = 0
@threshold_choice : Selection?
getter checked_nodes = 0
def knapsack_step(taken, items, remaining_weight)
if taken.total_value > @threshold_value
@threshold_value = taken.total_value
@threshold_choice = taken
end
candidate_index = items.index(taken.cur_index) { |item| item.weight <= remaining_weight }
return nil unless candidate_index
@checked_nodes += 1
candidate = items[candidate_index]
# candidate is a best of available items, so if we fill remaining value with
# and still don't reach the threshold, the branch is wrong
return nil if taken.total_value + 1.0 * candidate.value / candidate.weight * remaining_weight < @threshold_value
# now recursively check all variants (from taking maximum count to taking nothing)
max_count = {candidate.count, remaining_weight // candidate.weight}.min
(0..max_count).reverse_each do |n|
mask = taken.mask.clone
mask[candidate_index] = n
knapsack_step Selection.new(mask, candidate_index + 1, taken.total_value + n*candidate.value), items, remaining_weight - n*candidate.weight
end
end
def select(items, max_weight)
@checked_variants = 0
# sort by descending relative value
list = items.sort_by { |item| -1.0 * item.value / item.weight }
nothing = Selection.new(Array(Int32).new(items.size, 0), 0, 0)
@threshold_value = 0
@threshold_choice = nothing
knapsack_step(nothing, list, max_weight)
selected = @threshold_choice.not_nil!
result = Hash(Item, Int32).new(0)
selected.mask.each_with_index { |v, i| result[list[i]] = v if v > 0 }
result
end
end
possible = [
Item.new("map", 9, 150, 1),
Item.new("compass", 13, 35, 1),
Item.new("water", 153, 200, 2),
Item.new("sandwich", 50, 60, 2),
Item.new("glucose", 15, 60, 2),
Item.new("tin", 68, 45, 3),
Item.new("banana", 27, 60, 3),
Item.new("apple", 39, 40, 3),
Item.new("cheese", 23, 30, 1),
Item.new("beer", 52, 10, 3),
Item.new("suntan cream", 11, 70, 1),
Item.new("camera", 32, 30, 1),
Item.new("T-shirt", 24, 15, 2),
Item.new("trousers", 48, 10, 2),
Item.new("umbrella", 73, 40, 1),
Item.new("waterproof trousers", 42, 70, 1),
Item.new("waterproof overclothes", 43, 75, 1),
Item.new("note-case", 22, 80, 1),
Item.new("sunglasses", 7, 20, 1),
Item.new("towel", 18, 12, 2),
Item.new("socks", 4, 50, 1),
Item.new("book", 30, 10, 2),
]
solver = Knapsack.new
used = solver.select(possible, 400)
puts "optimal choice: #{used.map { |item, count| count == 1 ? item.name : "#{count}x #{item.name}" }.join(", ")}"
puts "total weight #{used.sum { |item, count| item.weight*count }}"
puts "total value #{used.sum { |item, count| item.value*count }}"
puts "checked nodes: #{solver.checked_nodes}"
- Output:
optimal choice: map, socks, suntan cream, 2x glucose, note-case, sunglasses, compass, 3x banana, waterproof overclothes, water, cheese total weight 396 total value 1010 checked nodes: 1185
Dynamic programming solution
# Item struct to represent each item in the problem
record Item, name : String, weight : Int32, value : Int32, count : Int32
def choose_item(items, weight, id, cache)
return 0, ([] of Int32) if id < 0
k = {weight, id}
cache = cache || {} of Tuple(Int32, Int32) => Tuple(Int32, Array(Int32))
return cache[k] if cache[k]?
value = items[id].value
best_v = 0
best_list = [] of Int32
(items[id].count + 1).times do |i|
wlim = weight - i * items[id].weight
break if wlim < 0
val, taken = choose_item(items, wlim, id - 1, cache)
if val + i * value > best_v
best_v = val + i * value
best_list = taken + [i]
end
end
cache[k] = {best_v, best_list}
return {best_v, best_list}
end
items = [
Item.new("map", 9, 150, 1),
Item.new("compass", 13, 35, 1),
Item.new("water", 153, 200, 2),
Item.new("sandwich", 50, 60, 2),
Item.new("glucose", 15, 60, 2),
Item.new("tin", 68, 45, 3),
Item.new("banana", 27, 60, 3),
Item.new("apple", 39, 40, 3),
Item.new("cheese", 23, 30, 1),
Item.new("beer", 52, 10, 3),
Item.new("suntan cream", 11, 70, 1),
Item.new("camera", 32, 30, 1),
Item.new("T-shirt", 24, 15, 2),
Item.new("trousers", 48, 10, 2),
Item.new("umbrella", 73, 40, 1),
Item.new("waterproof trousers", 42, 70, 1),
Item.new("waterproof overclothes", 43, 75, 1),
Item.new("note-case", 22, 80, 1),
Item.new("sunglasses", 7, 20, 1),
Item.new("towel", 18, 12, 2),
Item.new("socks", 4, 50, 1),
Item.new("book", 30, 10, 2),
]
val, list = choose_item(items, 400, items.size - 1, nil)
w = 0
list.each_with_index do |cnt, i|
if cnt > 0
print "#{cnt} #{items[i].name}\n"
w += items[i].weight * cnt
end
end
p "Total weight: #{w}, Value: #{val}"
D
Solution with memoization.
import std.stdio, std.typecons, std.functional;
immutable struct Item {
string name;
int weight, value, quantity;
}
immutable Item[] items = [
{"map", 9, 150, 1}, {"compass", 13, 35, 1},
{"water", 153, 200, 3}, {"sandwich", 50, 60, 2},
{"glucose", 15, 60, 2}, {"tin", 68, 45, 3},
{"banana", 27, 60, 3}, {"apple", 39, 40, 3},
{"cheese", 23, 30, 1}, {"beer", 52, 10, 3},
{"suntan cream", 11, 70, 1}, {"camera", 32, 30, 1},
{"t-shirt", 24, 15, 2}, {"trousers", 48, 10, 2},
{"umbrella", 73, 40, 1}, {"w-trousers", 42, 70, 1},
{"w-overcoat", 43, 75, 1}, {"note-case", 22, 80, 1},
{"sunglasses", 7, 20, 1}, {"towel", 18, 12, 2},
{"socks", 4, 50, 1}, {"book", 30, 10, 2}];
Tuple!(int, const(int)[]) chooseItem(in int iWeight, in int idx) nothrow @safe {
alias memoChooseItem = memoize!chooseItem;
if (idx < 0)
return typeof(return)();
int bestV;
const(int)[] bestList;
with (items[idx])
foreach (immutable i; 0 .. quantity + 1) {
immutable wlim = iWeight - i * weight;
if (wlim < 0)
break;
//const (val, taken) = memoChooseItem(wlim, idx - 1);
const val_taken = memoChooseItem(wlim, idx - 1);
if (val_taken[0] + i * value > bestV) {
bestV = val_taken[0] + i * value;
bestList = val_taken[1] ~ i;
}
}
return tuple(bestV, bestList);
}
void main() {
// const (v, lst) = chooseItem(400, items.length - 1);
const v_lst = chooseItem(400, items.length - 1);
int w;
foreach (immutable i, const cnt; v_lst[1])
if (cnt > 0) {
writeln(cnt, " ", items[i].name);
w += items[i].weight * cnt;
}
writeln("Total weight: ", w, " Value: ", v_lst[0]);
}
- Output:
1 map 1 compass 1 water 2 glucose 3 banana 1 cheese 1 suntan cream 1 w-overcoat 1 note-case 1 sunglasses 1 socks Total weight: 396 Value: 1010
EasyLang
name$[] = [ "map" "compass" "water" "sandwich" "glucose" "tin" "banana" "apple" "cheese" "beer" "suntan cream" "camera" "t-shirt" "trousers" "umbrella" "waterproof trousers" "waterproof overclothes" "note-case" "sunglasses" "towel" "socks" "book" ]
weight[] = [ 9 13 153 50 15 68 27 39 23 52 11 32 24 48 73 42 43 22 7 18 4 30 ]
value[] = [ 150 35 200 60 60 45 60 40 30 10 70 30 15 10 40 70 75 80 20 12 50 10 ]
pieces[] = [ 1 1 2 2 2 3 3 3 1 3 1 1 2 2 1 1 1 1 1 2 1 2 ]
maxweight = 400
#
global valuesum[] maxv .
#
proc solve i maxw v . items[] wres vres .
if i = 0
wres = 0
vres = 0
items[] = [ ]
maxv = higher maxv v
return
.
if v + valuesum[i] < maxv
vres = -100000
return
.
if weight[i] > maxw
solve i - 1 maxw v items[] wres vres
else
solve i - 1 maxw - weight[i] v + value[i] items1[] w1 v1
solve i - 1 maxw v items[] wres vres
if v1 + value[i] > vres
swap items[] items1[]
items[] &= i
wres = w1 + weight[i]
vres = v1 + value[i]
.
.
.
proc prepare . .
for i to len weight[]
for j to pieces[i]
n$[] &= name$[i]
w[] &= weight[i]
v[] &= value[i]
.
.
swap name$[] n$[]
swap weight[] w[]
swap value[] v[]
#
n = len weight[]
for i = 1 to n - 1
for j = i + 1 to n
if value[j] < value[i]
swap value[j] value[i]
swap weight[j] weight[i]
swap name$[j] name$[i]
.
.
.
for i to n
s += value[i]
valuesum[] &= s
.
.
prepare
#
solve len weight[] maxweight 0 items[] wsum vsum
print "weight: " & wsum & " value: " & vsum
print "items:"
for item in items[]
print " " & name$[item]
.
- Output:
weight: 396 value: 1010 items: sunglasses cheese compass socks banana banana glucose glucose banana suntan cream waterproof overclothes note-case map water
EchoLisp
We convert the problem to a Knapsack-0/1 problem by replacing (n-max item) vith n-max identical occurences of 1 item.
(lib 'struct)
(lib 'sql)
(lib 'hash)
(define H (make-hash))
(define T (make-table (struct goodies (name poids valeur qty))))
(define IDX (make-vector 0))
;; convert to 0/1 PB
;; transorm vector [1 2 3 4 (n-max 3) 5 (n-max 2) 6 .. ]
;; into vector of repeated indices : [1 2 3 4 4 4 5 5 6 ... ]
(define (make-01 T)
(for ((record T) (i (in-naturals)))
(for ((j (in-range 0 (goodies-qty record))))
(vector-push IDX i)))
IDX)
(define-syntax-rule (name i) (table-xref T (vector-ref IDX i) 0))
(define-syntax-rule (poids i) (table-xref T (vector-ref IDX i) 1))
(define-syntax-rule (valeur i) (table-xref T (vector-ref IDX i) 2))
;;
;; code identical to 0/1 problem
;;
;; make an unique hash-key from (i rest)
(define (t-idx i r) (string-append i "|" r))
;; retrieve best core for item i, remaining r availbble weight
(define (t-get i r) (or (hash-ref H (t-idx i r)) 0))
;; compute best score (i), assuming best (i-1 rest) is known
(define (score i restant)
(if (< i 0) 0
(hash-ref! H (t-idx i restant)
(if ( >= restant (poids i))
(max
(score (1- i) restant)
(+ (score (1- i) (- restant (poids i))) (valeur i)))
(score (1- i) restant)) ;; else not enough
)))
;; compute best scores, starting from last item
(define (task W)
(define restant W)
(make-01 T)
(define N (1- (vector-length IDX)))
(writeln 'total-value (score N W))
(group
(for/list ((i (in-range N -1 -1)))
#:continue (= (t-get i restant) (t-get (1- i) restant))
(set! restant (- restant (poids i)))
(name i))))
- Output:
(define goodies
'((map 9 150 1) (compass 13 35 1)(water 153 200 3)
(sandwich 50 60 2)(🍰-glucose 15 60 2)(tin 68 45 3)
(🍌-banana 27 60 3)(🍎-apple 39 40 3)(cheese 23 30 1)
(beer 52 10 3)(🌞-suntan-cream 11 70 1)(camera 32 30 1)
(t-shirt 24 15 2)(trousers 48 10 2)(umbrella 73 40 1)
(☔️-trousers 42 70 1)(☔️--overcoat 43 75 1)(note-case 22 80 1)
(🌞-sunglasses 7 20 1)(towel 18 12 2)(socks 4 50 1)
(book 30 10 2)))
(list->table goodies T)
(task 400)
total-value 1010
→ ((socks) (🌞-sunglasses) (note-case) (☔️--overcoat) (🌞-suntan-cream) (cheese)
(🍌-banana 🍌-banana 🍌-banana) (🍰-glucose 🍰-glucose) (water) (compass) (map))
(length (hash-keys H))
→ 10827 ;; # of entries in cache
FreeBASIC
#define PesoMax 400
#define items 22
#define Tabu Chr(9)
Type Knapsack
articulo As String*22
peso As Integer
valor As Integer
pieza As Integer
End Type
Dim item(1 To 22) As Knapsack => { _
("map ", 9, 150, 0), ("compass ", 13, 35, 0), _
("water ", 153, 200, 0), ("sandwich ", 50, 160, 0), _
("glucose ", 15, 60, 0), ("tin ", 68, 45, 0), _
("banana ", 27, 60, 0), ("apple ", 39, 40, 0), _
("cheese ", 23, 30, 0), ("beer ", 52, 10, 0), _
("suntan cream ", 11, 70, 0), ("camera ", 32, 30, 0), _
("T-shirt ", 24, 15, 0), ("trousers ", 48, 10, 0), _
("umbrella ", 73, 40, 0), ("waterproof trousers ", 42, 70, 0), _
("waterproof overclothes", 43, 75, 0), ("note-case ", 22, 80, 0), _
("sunglasses ", 7, 20, 0), ("towel ", 18, 12, 0), _
("socks ", 4, 50, 0), ("book ", 30, 10, 0)}
Dim As Integer i, tot = 0, TValor = 0
For i =1 To Ubound(item)
tot += item(i).peso
Next i
Dim As Integer TPeso = tot-PesoMax
Dim As String pr = ""
Dim As Integer c = 0, v, w, k
Do
v = 1e9 : w = 0 : k = 0
For i = 1 To items
If item(i).pieza = 0 Then
w = 1000 * item(i).valor / item(i).peso
If w < v Then v = w : k = i
End If
Next i
If k Then
TPeso -= item(k).peso
item(k).pieza = 1
If TPeso <= 0 Then Exit Do
End If
c += 1
Loop Until c>= items
Print "Knapsack contents: "
For i = 1 To items
If item(i).pieza = 0 Then
Print item(i).articulo & Tabu & item(i).peso & Tabu & item(i).valor
TValor += item(i).valor
End If
Next i
Print !"\nTotal value: "; TValor
Print "Total weight: "; PesoMax + TPeso
Sleep
- Output:
Knapsack contents: map 9 150 compass 13 35 water 153 200 sandwich 50 160 glucose 15 60 banana 27 60 suntan cream 11 70 waterproof trousers 42 70 waterproof overclothes 43 75 note-case 22 80 sunglasses 7 20 socks 4 50 Total value: 1030 Total weight: 396
Go
Solution with caching.
package main
import "fmt"
type Item struct {
name string
weight, value, qty int
}
var items = []Item{
{"map", 9, 150, 1},
{"compass", 13, 35, 1},
{"water", 153, 200, 2},
{"sandwich", 50, 60, 2},
{"glucose", 15, 60, 2},
{"tin", 68, 45, 3},
{"banana", 27, 60, 3},
{"apple", 39, 40, 3},
{"cheese", 23, 30, 1},
{"beer", 52, 10, 3},
{"suntancream", 11, 70, 1},
{"camera", 32, 30, 1},
{"T-shirt", 24, 15, 2},
{"trousers", 48, 10, 2},
{"umbrella", 73, 40, 1},
{"w-trousers", 42, 70, 1},
{"w-overclothes", 43, 75, 1},
{"note-case", 22, 80, 1},
{"sunglasses", 7, 20, 1},
{"towel", 18, 12, 2},
{"socks", 4, 50, 1},
{"book", 30, 10, 2},
}
type Chooser struct {
Items []Item
cache map[key]solution
}
type key struct {
w, p int
}
type solution struct {
v, w int
qty []int
}
func (c Chooser) Choose(limit int) (w, v int, qty []int) {
c.cache = make(map[key]solution)
s := c.rchoose(limit, len(c.Items)-1)
c.cache = nil // allow cache to be garbage collected
return s.v, s.w, s.qty
}
func (c Chooser) rchoose(limit, pos int) solution {
if pos < 0 || limit <= 0 {
return solution{0, 0, nil}
}
key := key{limit, pos}
if s, ok := c.cache[key]; ok {
return s
}
best_i, best := 0, solution{0, 0, nil}
for i := 0; i*items[pos].weight <= limit && i <= items[pos].qty; i++ {
sol := c.rchoose(limit-i*items[pos].weight, pos-1)
sol.v += i * items[pos].value
if sol.v > best.v {
best_i, best = i, sol
}
}
if best_i > 0 {
// best.qty is used in another cache entry,
// we need to duplicate it before modifying it to
// store as our cache entry.
old := best.qty
best.qty = make([]int, len(items))
copy(best.qty, old)
best.qty[pos] = best_i
best.w += best_i * items[pos].weight
}
c.cache[key] = best
return best
}
func main() {
v, w, s := Chooser{Items: items}.Choose(400)
fmt.Println("Taking:")
for i, t := range s {
if t > 0 {
fmt.Printf(" %d of %d %s\n", t, items[i].qty, items[i].name)
}
}
fmt.Printf("Value: %d; weight: %d\n", v, w)
}
(A simple test and benchmark used while making changes to make sure performance wasn't sacrificed is available at /Go_test.)
- Output:
Taking: 1 of 1 map 1 of 1 compass 1 of 2 water 2 of 2 glucose 3 of 3 banana 1 of 1 cheese 1 of 1 suntancream 1 of 1 w-overclothes 1 of 1 note-case 1 of 1 sunglasses 1 of 1 socks Value: 1010; weight: 396
Groovy
Solution: dynamic programming
def totalWeight = { list -> list.collect{ it.item.weight * it.count }.sum() }
def totalValue = { list -> list.collect{ it.item.value * it.count }.sum() }
def knapsackBounded = { possibleItems ->
def n = possibleItems.size()
def m = (0..n).collect{ i -> (0..400).collect{ w -> []} }
(1..400).each { w ->
(1..n).each { i ->
def item = possibleItems[i-1]
def wi = item.weight, pi = item.pieces
def bi = [w.intdiv(wi),pi].min()
m[i][w] = (0..bi).collect{ count ->
m[i-1][w - wi * count] + [[item:item, count:count]]
}.max(totalValue).findAll{ it.count }
}
}
m[n][400]
}
Test:
def items = [
[name:"map", weight: 9, value:150, pieces:1],
[name:"compass", weight: 13, value: 35, pieces:1],
[name:"water", weight:153, value:200, pieces:2],
[name:"sandwich", weight: 50, value: 60, pieces:2],
[name:"glucose", weight: 15, value: 60, pieces:2],
[name:"tin", weight: 68, value: 45, pieces:3],
[name:"banana", weight: 27, value: 60, pieces:3],
[name:"apple", weight: 39, value: 40, pieces:3],
[name:"cheese", weight: 23, value: 30, pieces:1],
[name:"beer", weight: 52, value: 10, pieces:3],
[name:"suntan cream", weight: 11, value: 70, pieces:1],
[name:"camera", weight: 32, value: 30, pieces:1],
[name:"t-shirt", weight: 24, value: 15, pieces:2],
[name:"trousers", weight: 48, value: 10, pieces:2],
[name:"umbrella", weight: 73, value: 40, pieces:1],
[name:"waterproof trousers", weight: 42, value: 70, pieces:1],
[name:"waterproof overclothes", weight: 43, value: 75, pieces:1],
[name:"note-case", weight: 22, value: 80, pieces:1],
[name:"sunglasses", weight: 7, value: 20, pieces:1],
[name:"towel", weight: 18, value: 12, pieces:2],
[name:"socks", weight: 4, value: 50, pieces:1],
[name:"book", weight: 30, value: 10, pieces:2],
]
def start = System.currentTimeMillis()
def packingList = knapsackBounded(items)
def elapsed = System.currentTimeMillis() - start
println "Elapsed Time: ${elapsed/1000.0} s"
println "Total Weight: ${totalWeight(packingList)}"
println " Total Value: ${totalValue(packingList)}"
packingList.each {
printf (' item: %-22s weight:%4d value:%4d count:%2d\n',
it.item.name, it.item.weight, it.item.value, it.count)
}
- Output:
Elapsed Time: 0.603 s Total Weight: 396 Total Value: 1010 item: map weight: 9 value: 150 count: 1 item: compass weight: 13 value: 35 count: 1 item: water weight: 153 value: 200 count: 1 item: glucose weight: 15 value: 60 count: 2 item: banana weight: 27 value: 60 count: 3 item: cheese weight: 23 value: 30 count: 1 item: suntan cream weight: 11 value: 70 count: 1 item: waterproof overclothes weight: 43 value: 75 count: 1 item: note-case weight: 22 value: 80 count: 1 item: sunglasses weight: 7 value: 20 count: 1 item: socks weight: 4 value: 50 count: 1
Haskell
Directly lifted from 1-0 problem:
inv = [("map",9,150,1), ("compass",13,35,1), ("water",153,200,2), ("sandwich",50,60,2),
("glucose",15,60,2), ("tin",68,45,3), ("banana",27,60,3), ("apple",39,40,3),
("cheese",23,30,1), ("beer",52,10,3), ("cream",11,70,1), ("camera",32,30,1),
-- what to do if we end up taking one trouser?
("tshirt",24,15,2), ("trousers",48,10,2), ("umbrella",73,40,1), ("wtrousers",42,70,1),
("woverclothes",43,75,1), ("notecase",22,80,1), ("sunglasses",7,20,1), ("towel",18,12,2),
("socks",4,50,1), ("book",30,10,2)]
knapsack = foldr addItem (repeat (0,[])) where
addItem (name,w,v,c) old = foldr inc old [1..c] where
inc i list = left ++ zipWith max right new where
(left, right) = splitAt (w * i) list
new = map (\(val,itms)->(val + v * i, (name,i):itms)) old
main = print $ (knapsack inv) !! 400
- Output:
(1010,[("socks",1),("sunglasses",1),("notecase",1),("woverclothes",1),("cream",1),("cheese",1),("banana",3),("glucose",2),("water",1),("compass",1),("map",1)])
The above uses merging lists for cache. It's faster, and maybe easier to understand when some constant-time lookup structure is used for cache (same output):
import Data.Array
-- snipped the item list; use the one from above
knapsack items cap = (solu items) ! cap where
solu = foldr f (listArray (0,cap) (repeat (0,[])))
f (name,w,v,cnt) ss = listArray (0,cap) $ map optimal [0..] where
optimal ww = maximum $ (ss!ww):[prepend (v*i,(name,i)) (ss!(ww - i*w))
| i <- [1..cnt], i*w < ww]
prepend (x,n) (y,s) = (x+y,n:s)
main = do print $ knapsack inv 400
J
Brute force solution:
'names numbers'=:|:".;._2]0 :0
'map'; 9 150 1
'compass'; 13 35 1
'water'; 153 200 2
'sandwich'; 50 60 2
'glucose'; 15 60 2
'tin'; 68 45 3
'banana'; 27 60 3
'apple'; 39 40 3
'cheese'; 23 30 1
'beer'; 52 10 3
'suntan cream'; 11 70 1
'camera'; 32 30 1
'T-shirt'; 24 15 2
'trousers'; 48 10 2
'umbrella'; 73 40 1
'waterproof trousers'; 42 70 1
'waterproof overclothes'; 43 75 1
'note-case'; 22 80 1
'sunglasses'; 7 20 1
'towel'; 18 12 2
'socks'; 4 50 1
'book'; 30 10 2
)
'weights values pieces'=:|:numbers
decode=: (pieces+1)&#:
pickBest=:4 :0
NB. given a list of options, return the best option(s)
n=. decode y
weight=. n+/ .*weights
value=. (x >: weight) * n+/ .*values
(value = >./value)#y
)
bestCombo=:3 :0
limit=. */pieces+1
i=. 0
step=. 1e6
best=. ''
while.i<limit do.
best=. 400 pickBest best,(#~ limit&>)i+i.step
i=. i+step
end.
best
)
bestCombo''
978832641
Interpretation of answer:
decode 978832641
1 1 1 0 2 0 3 0 1 0 1 0 0 0 0 0 1 1 1 0 1 0
(0<decode 978832641) # (":,.decode 978832641),.' ',.names
1 map
1 compass
1 water
2 glucose
3 banana
1 cheese
1 suntan cream
1 waterproof overclothes
1 note-case
1 sunglasses
1 socks
weights +/ .* decode 978832641
396
values +/ .* decode 978832641
1010
Dynamic programming solution (faster):
dyn=:3 :0
m=. 0$~1+400,+/pieces NB. maximum value cache
b=. m NB. best choice cache
opts=.+/\0,pieces NB. distinct item counts before each piece
P=. */\1+0,pieces NB. distinct possibilities before each piece
for_w.1+i.400 do.
for_j.i.#pieces do.
n=. i.1+j{pieces NB. possible counts for this piece
W=. n*j{weights NB. how much they weigh
s=. w>:W NB. permissible options
v=. s*n*j{values NB. consequent values
base=. j{opts NB. base index for these options
I=. <"1 w,.n+base NB. consequent indices
i0=. <w,base NB. status quo index
iN=. <"1 (w-s*W),.base NB. predecessor indices
M=. >./\(m{~i0)>.v+m{~iN NB. consequent maximum values
C=. (n*j{P)+b{~iN NB. unique encoding for each option
B=. >./\(b{~i0)>. C * 2 ~:/\ 0,M NB. best options, so far
m=. M I} m NB. update with newly computed maxima
b=. B I} b NB. same for best choice
end.
end.
|.(1+|.pieces)#:{:{:b
)
dyn''
1 1 1 0 2 0 3 0 1 0 1 0 0 0 0 0 1 1 1 0 1 0
Note: the brute force approach would return multiple "best answers" if more than one combination of choices would satisfy the "best" constraint. The dynamic approach arbitrarily picks one of those choices. That said, with this particular choice of item weights and values, this is an irrelevant distinction.
Java
General dynamic solution after wikipedia. The solution extends the method of Knapsack problem/0-1#Java .
package hu.pj.alg.test;
import hu.pj.alg.BoundedKnapsack;
import hu.pj.obj.Item;
import java.util.*;
import java.text.*;
public class BoundedKnapsackForTourists {
public BoundedKnapsackForTourists() {
BoundedKnapsack bok = new BoundedKnapsack(400); // 400 dkg = 400 dag = 4 kg
// making the list of items that you want to bring
bok.add("map", 9, 150, 1);
bok.add("compass", 13, 35, 1);
bok.add("water", 153, 200, 3);
bok.add("sandwich", 50, 60, 2);
bok.add("glucose", 15, 60, 2);
bok.add("tin", 68, 45, 3);
bok.add("banana", 27, 60, 3);
bok.add("apple", 39, 40, 3);
bok.add("cheese", 23, 30, 1);
bok.add("beer", 52, 10, 3);
bok.add("suntan cream", 11, 70, 1);
bok.add("camera", 32, 30, 1);
bok.add("t-shirt", 24, 15, 2);
bok.add("trousers", 48, 10, 2);
bok.add("umbrella", 73, 40, 1);
bok.add("waterproof trousers", 42, 70, 1);
bok.add("waterproof overclothes", 43, 75, 1);
bok.add("note-case", 22, 80, 1);
bok.add("sunglasses", 7, 20, 1);
bok.add("towel", 18, 12, 2);
bok.add("socks", 4, 50, 1);
bok.add("book", 30, 10, 2);
// calculate the solution:
List<Item> itemList = bok.calcSolution();
// write out the solution in the standard output
if (bok.isCalculated()) {
NumberFormat nf = NumberFormat.getInstance();
System.out.println(
"Maximal weight = " +
nf.format(bok.getMaxWeight() / 100.0) + " kg"
);
System.out.println(
"Total weight of solution = " +
nf.format(bok.getSolutionWeight() / 100.0) + " kg"
);
System.out.println(
"Total value = " +
bok.getProfit()
);
System.out.println();
System.out.println(
"You can carry te following materials " +
"in the knapsack:"
);
for (Item item : itemList) {
if (item.getInKnapsack() > 0) {
System.out.format(
"%1$-10s %2$-23s %3$-3s %4$-5s %5$-15s \n",
item.getInKnapsack() + " unit(s) ",
item.getName(),
item.getInKnapsack() * item.getWeight(), "dag ",
"(value = " + item.getInKnapsack() * item.getValue() + ")"
);
}
}
} else {
System.out.println(
"The problem is not solved. " +
"Maybe you gave wrong data."
);
}
}
public static void main(String[] args) {
new BoundedKnapsackForTourists();
}
} // class
package hu.pj.alg;
import hu.pj.obj.Item;
import java.util.*;
public class BoundedKnapsack extends ZeroOneKnapsack {
public BoundedKnapsack() {}
public BoundedKnapsack(int _maxWeight) {
setMaxWeight(_maxWeight);
}
public BoundedKnapsack(List<Item> _itemList) {
setItemList(_itemList);
}
public BoundedKnapsack(List<Item> _itemList, int _maxWeight) {
setItemList(_itemList);
setMaxWeight(_maxWeight);
}
@Override
public List<Item> calcSolution() {
int n = itemList.size();
// add items to the list, if bounding > 1
for (int i = 0; i < n; i++) {
Item item = itemList.get(i);
if (item.getBounding() > 1) {
for (int j = 1; j < item.getBounding(); j++) {
add(item.getName(), item.getWeight(), item.getValue());
}
}
}
super.calcSolution();
// delete the added items, and increase the original items
while (itemList.size() > n) {
Item lastItem = itemList.get(itemList.size() - 1);
if (lastItem.getInKnapsack() == 1) {
for (int i = 0; i < n; i++) {
Item iH = itemList.get(i);
if (lastItem.getName().equals(iH.getName())) {
iH.setInKnapsack(1 + iH.getInKnapsack());
break;
}
}
}
itemList.remove(itemList.size() - 1);
}
return itemList;
}
// add an item to the item list
public void add(String name, int weight, int value, int bounding) {
if (name.equals(""))
name = "" + (itemList.size() + 1);
itemList.add(new Item(name, weight, value, bounding));
setInitialStateForCalculation();
}
} // class
package hu.pj.alg;
import hu.pj.obj.Item;
import java.util.*;
public class ZeroOneKnapsack {
protected List<Item> itemList = new ArrayList<Item>();
protected int maxWeight = 0;
protected int solutionWeight = 0;
protected int profit = 0;
protected boolean calculated = false;
public ZeroOneKnapsack() {}
public ZeroOneKnapsack(int _maxWeight) {
setMaxWeight(_maxWeight);
}
public ZeroOneKnapsack(List<Item> _itemList) {
setItemList(_itemList);
}
public ZeroOneKnapsack(List<Item> _itemList, int _maxWeight) {
setItemList(_itemList);
setMaxWeight(_maxWeight);
}
// calculte the solution of 0-1 knapsack problem with dynamic method:
public List<Item> calcSolution() {
int n = itemList.size();
setInitialStateForCalculation();
if (n > 0 && maxWeight > 0) {
List< List<Integer> > c = new ArrayList< List<Integer> >();
List<Integer> curr = new ArrayList<Integer>();
c.add(curr);
for (int j = 0; j <= maxWeight; j++)
curr.add(0);
for (int i = 1; i <= n; i++) {
List<Integer> prev = curr;
c.add(curr = new ArrayList<Integer>());
for (int j = 0; j <= maxWeight; j++) {
if (j > 0) {
int wH = itemList.get(i-1).getWeight();
curr.add(
(wH > j)
?
prev.get(j)
:
Math.max(
prev.get(j),
itemList.get(i-1).getValue() + prev.get(j-wH)
)
);
} else {
curr.add(0);
}
} // for (j...)
} // for (i...)
profit = curr.get(maxWeight);
for (int i = n, j = maxWeight; i > 0 && j >= 0; i--) {
int tempI = c.get(i).get(j);
int tempI_1 = c.get(i-1).get(j);
if (
(i == 0 && tempI > 0)
||
(i > 0 && tempI != tempI_1)
)
{
Item iH = itemList.get(i-1);
int wH = iH.getWeight();
iH.setInKnapsack(1);
j -= wH;
solutionWeight += wH;
}
} // for()
calculated = true;
} // if()
return itemList;
}
// add an item to the item list
public void add(String name, int weight, int value) {
if (name.equals(""))
name = "" + (itemList.size() + 1);
itemList.add(new Item(name, weight, value));
setInitialStateForCalculation();
}
// add an item to the item list
public void add(int weight, int value) {
add("", weight, value); // the name will be "itemList.size() + 1"!
}
// remove an item from the item list
public void remove(String name) {
for (Iterator<Item> it = itemList.iterator(); it.hasNext(); ) {
if (name.equals(it.next().getName())) {
it.remove();
}
}
setInitialStateForCalculation();
}
// remove all items from the item list
public void removeAllItems() {
itemList.clear();
setInitialStateForCalculation();
}
public int getProfit() {
if (!calculated)
calcSolution();
return profit;
}
public int getSolutionWeight() {return solutionWeight;}
public boolean isCalculated() {return calculated;}
public int getMaxWeight() {return maxWeight;}
public void setMaxWeight(int _maxWeight) {
maxWeight = Math.max(_maxWeight, 0);
}
public void setItemList(List<Item> _itemList) {
if (_itemList != null) {
itemList = _itemList;
for (Item item : _itemList) {
item.checkMembers();
}
}
}
// set the member with name "inKnapsack" by all items:
private void setInKnapsackByAll(int inKnapsack) {
for (Item item : itemList)
if (inKnapsack > 0)
item.setInKnapsack(1);
else
item.setInKnapsack(0);
}
// set the data members of class in the state of starting the calculation:
protected void setInitialStateForCalculation() {
setInKnapsackByAll(0);
calculated = false;
profit = 0;
solutionWeight = 0;
}
} // class
package hu.pj.obj;
public class Item {
protected String name = "";
protected int weight = 0;
protected int value = 0;
protected int bounding = 1; // the maximal limit of item's pieces
protected int inKnapsack = 0; // the pieces of item in solution
public Item() {}
public Item(Item item) {
setName(item.name);
setWeight(item.weight);
setValue(item.value);
setBounding(item.bounding);
}
public Item(int _weight, int _value) {
setWeight(_weight);
setValue(_value);
}
public Item(int _weight, int _value, int _bounding) {
setWeight(_weight);
setValue(_value);
setBounding(_bounding);
}
public Item(String _name, int _weight, int _value) {
setName(_name);
setWeight(_weight);
setValue(_value);
}
public Item(String _name, int _weight, int _value, int _bounding) {
setName(_name);
setWeight(_weight);
setValue(_value);
setBounding(_bounding);
}
public void setName(String _name) {name = _name;}
public void setWeight(int _weight) {weight = Math.max(_weight, 0);}
public void setValue(int _value) {value = Math.max(_value, 0);}
public void setInKnapsack(int _inKnapsack) {
inKnapsack = Math.min(getBounding(), Math.max(_inKnapsack, 0));
}
public void setBounding(int _bounding) {
bounding = Math.max(_bounding, 0);
if (bounding == 0)
inKnapsack = 0;
}
public void checkMembers() {
setWeight(weight);
setValue(value);
setBounding(bounding);
setInKnapsack(inKnapsack);
}
public String getName() {return name;}
public int getWeight() {return weight;}
public int getValue() {return value;}
public int getInKnapsack() {return inKnapsack;}
public int getBounding() {return bounding;}
} // class
- Output:
Maximal weight = 4 kg Total weight of solution = 3,96 kg Total value = 1010 You can carry te following materials in the knapsack: 1 unit(s) map 9 dag (value = 150) 1 unit(s) compass 13 dag (value = 35) 1 unit(s) water 153 dag (value = 200) 2 unit(s) glucose 30 dag (value = 120) 3 unit(s) banana 81 dag (value = 180) 1 unit(s) cheese 23 dag (value = 30) 1 unit(s) suntan cream 11 dag (value = 70) 1 unit(s) waterproof overclothes 43 dag (value = 75) 1 unit(s) note-case 22 dag (value = 80) 1 unit(s) sunglasses 7 dag (value = 20) 1 unit(s) socks 4 dag (value = 50)
JavaScript
Based on the (dynamic) J implementation. Expressed as an htm page:
<html><head><title></title></head><body></body></html>
<script type="text/javascript">
var data= [
{name: 'map', weight: 9, value:150, pieces:1},
{name: 'compass', weight: 13, value: 35, pieces:1},
{name: 'water', weight:153, value:200, pieces:2},
{name: 'sandwich', weight: 50, value: 60, pieces:2},
{name: 'glucose', weight: 15, value: 60, pieces:2},
{name: 'tin', weight: 68, value: 45, pieces:3},
{name: 'banana', weight: 27, value: 60, pieces:3},
{name: 'apple', weight: 39, value: 40, pieces:3},
{name: 'cheese', weight: 23, value: 30, pieces:1},
{name: 'beer', weight: 52, value: 10, pieces:3},
{name: 'suntan, cream', weight: 11, value: 70, pieces:1},
{name: 'camera', weight: 32, value: 30, pieces:1},
{name: 'T-shirt', weight: 24, value: 15, pieces:2},
{name: 'trousers', weight: 48, value: 10, pieces:2},
{name: 'umbrella', weight: 73, value: 40, pieces:1},
{name: 'waterproof, trousers', weight: 42, value: 70, pieces:1},
{name: 'waterproof, overclothes',weight: 43, value: 75, pieces:1},
{name: 'note-case', weight: 22, value: 80, pieces:1},
{name: 'sunglasses', weight: 7, value: 20, pieces:1},
{name: 'towel', weight: 18, value: 12, pieces:2},
{name: 'socks', weight: 4, value: 50, pieces:1},
{name: 'book', weight: 30, value: 10, pieces:2}
];
function findBestPack() {
var m= [[0]]; // maximum pack value found so far
var b= [[0]]; // best combination found so far
var opts= [0]; // item index for 0 of item 0
var P= [1]; // item encoding for 0 of item 0
var choose= 0;
for (var j= 0; j<data.length; j++) {
opts[j+1]= opts[j]+data[j].pieces; // item index for 0 of item j+1
P[j+1]= P[j]*(1+data[j].pieces); // item encoding for 0 of item j+1
}
for (var j= 0; j<opts[data.length]; j++) {
m[0][j+1]= b[0][j+1]= 0; // best values and combos for empty pack: nothing
}
for (var w=1; w<=400; w++) {
m[w]= [0];
b[w]= [0];
for (var j=0; j<data.length; j++) {
var N= data[j].pieces; // how many of these can we have?
var base= opts[j]; // what is the item index for 0 of these?
for (var n= 1; n<=N; n++) {
var W= n*data[j].weight; // how much do these items weigh?
var s= w>=W ?1 :0; // can we carry this many?
var v= s*n*data[j].value; // how much are they worth?
var I= base+n; // what is the item number for this many?
var wN= w-s*W; // how much other stuff can we be carrying?
var C= n*P[j] + b[wN][base]; // encoded combination
m[w][I]= Math.max(m[w][I-1], v+m[wN][base]); // best value
choose= b[w][I]= m[w][I]>m[w][I-1] ?C :b[w][I-1];
}
}
}
var best= [];
for (var j= data.length-1; j>=0; j--) {
best[j]= Math.floor(choose/P[j]);
choose-= best[j]*P[j];
}
var out='<table><tr><td><b>Count</b></td><td><b>Item</b></td><th>unit weight</th><th>unit value</th>';
var wgt= 0;
var val= 0;
for (var i= 0; i<best.length; i++) {
if (0==best[i]) continue;
out+='</tr><tr><td>'+best[i]+'</td><td>'+data[i].name+'</td><td>'+data[i].weight+'</td><td>'+data[i].value+'</td>'
wgt+= best[i]*data[i].weight;
val+= best[i]*data[i].value;
}
out+= '</tr></table><br/>Total weight: '+wgt;
out+= '<br/>Total value: '+val;
document.body.innerHTML= out;
}
findBestPack();
</script>
This will generate (translating html to mediawiki markup):
| Count | Item | unit weight | unit value |
|---|---|---|---|
| 1 | map | 9 | 150 |
| 1 | compass | 13 | 35 |
| 1 | water | 153 | 200 |
| 2 | glucose | 15 | 60 |
| 3 | banana | 27 | 60 |
| 1 | cheese | 23 | 30 |
| 1 | suntan, cream | 11 | 70 |
| 1 | waterproof, overclothes | 43 | 75 |
| 1 | note-case | 22 | 80 |
| 1 | sunglasses | 7 | 20 |
| 1 | socks | 4 | 50 |
Total weight: 396
Total value: 1010
jq
Adapted from Wren
Works with gojq, the Go implementation of jq
# Item {name, weight, value, count}
def Item($name; $weight; $value; $count): {$name, $weight, $value, $count};
def items: [
Item("map"; 9; 150; 1),
Item("compass"; 13; 35; 1),
Item("water"; 153; 200; 2),
Item("sandwich"; 50; 60; 2),
Item("glucose"; 15; 60; 2),
Item("tin"; 68; 45; 3),
Item("banana"; 27; 60; 3),
Item("apple"; 39; 40; 3),
Item("cheese"; 23; 30; 1),
Item("beer"; 52; 10; 3),
Item("suntan cream"; 11; 70; 1),
Item("camera"; 32; 30; 1),
Item("T-shirt"; 24; 15; 2),
Item("trousers"; 48; 10; 2),
Item("umbrella"; 73; 40; 1),
Item("waterproof trousers"; 42; 70; 1),
Item("waterproof overclothes"; 43; 75; 1),
Item("note-case"; 22; 80; 1),
Item("sunglasses"; 7; 20; 1),
Item("towel"; 18; 12; 2),
Item("socks"; 4; 50; 1),
Item("book"; 30; 10; 2)
];
def knapsack($w):
def list($init): [range(0; .) | $init];
(items|length) as $n
| {m: ($n+1 | list( $w + 1 | list(0) )) }
| reduce range(1; $n+1) as $i (.;
reduce range (0; $w + 1) as $j (.;
.m[$i][$j] = .m[$i-1][$j]
| label $out
| foreach (range(1; 1 + ((items[$i - 1].count))), null) as $k (.stop = false;
if $k == null then .
elif ($k * items[$i - 1].weight > $j) then .stop = true
else (.m[$i - 1][$j - ($k * items[$i - 1].weight)] + $k * items[$i - 1].value) as $v
| if $v > .m[$i][$j] then .m[$i][$j] = $v else . end
end;
if .stop or ($k == null) then ., break $out else empty end)
) )
| .s = ($n|list(0))
| .j = $w
| reduce range($n; 0; -1) as $i (.;
.m[$i][.j] as $v
| .k = 0
| until ($v == .m[$i - 1][.j] + .k * items[$i - 1].value;
.s[$i - 1] += 1
| .j = .j - items[$i - 1].weight
| .k += 1 ) )
| .s;
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
def task(maxWeight):
def f(a;b;c;d): "\(a|lpad(22)) \(b|lpad(6)) \(c|lpad(6)) \(d|lpad(6))";
def f: . as [$a,$b,$c,$d] | f($a;$b;$c;$d);
(items|length) as $n
| knapsack(maxWeight) as $s
| f("Item Chosen"; "Weight";"Value";"Number"),
"---------------------- ------ ----- ------",
({ itemCount:0,
sumWeight:0,
sumValue :0,
sumNumber:0 }
| reduce range(0; $n) as $i (.;
if ($s[$i] != 0)
then .itemCount += 1
| .name = items[$i].name
| .number = $s[$i]
| .weight = items[$i].weight * .number
| .value = items[$i].value * .number
| .sumNumber += .number
| .sumWeight += .weight
| .sumValue += .value
| .emit += [[.name, .weight, .value, .number]]
else .
end )
| (.emit[] | f),
"---------------------- ------ ----- ------",
f("Items chosen \(.itemCount|lpad(4))"; .sumWeight; .sumValue; .sumNumber) );
task(400)- Output:
Item Chosen Weight Value Number
---------------------- ------ ----- ------
map 9 150 1
compass 13 35 1
water 153 200 1
glucose 30 120 2
banana 81 180 3
cheese 23 30 1
suntan cream 11 70 1
waterproof overclothes 43 75 1
note-case 22 80 1
sunglasses 7 20 1
socks 4 50 1
---------------------- ------ ----- ------
Items chosen 11 396 1010 14
Julia
The solution uses Julia's MathProgBase. Most of the work is done with this package's mixintprog function.
Type and Function:
using MathProgBase, Cbc
struct KPDSupply{T<:Integer}
item::String
weight::T
value::T
quant::T
end
Base.show(io::IO, kdps::KPDSupply) = print(io, kdps.quant, " ", kdps.item, " ($(kdps.weight) kg, $(kdps.value) €)")
function solve(gear::Vector{KPDSupply{T}}, capacity::Integer) where T<:Integer
w = getfield.(gear, :weight)
v = getfield.(gear, :value)
q = getfield.(gear, :quant)
sol = mixintprog(-v, w', '<', capacity, :Int, 0, q, CbcSolver())
sol.status == :Optimal || error("this problem could not be solved")
if all(q .== 1) # simpler case
return gear[sol.sol == 1.0]
else
pack = similar(gear, 0)
s = round.(Int, sol.sol)
for (i, g) in enumerate(gear)
iszero(s[i]) && continue
push!(pack, KPDSupply(g.item, g.weight, g.value, s[i]))
end
return pack
end
end
Main:
gear = [KPDSupply("map", 9, 150, 1),
KPDSupply("compass", 13, 35, 1),
KPDSupply("water", 153, 200, 2),
KPDSupply("sandwich", 50, 60, 2),
KPDSupply("glucose", 15, 60, 2),
KPDSupply("tin", 68, 45, 3),
KPDSupply("banana", 27, 60, 3),
KPDSupply("apple", 39, 40, 3),
KPDSupply("cheese", 23, 30, 1),
KPDSupply("beer", 52, 10, 3),
KPDSupply("suntan cream", 11, 70, 1),
KPDSupply("camera", 32, 30, 1),
KPDSupply("T-shirt", 24, 15, 2),
KPDSupply("trousers", 48, 10, 2),
KPDSupply("umbrella", 73, 40, 1),
KPDSupply("waterproof trousers", 42, 70, 1),
KPDSupply("waterproof overclothes", 43, 75, 1),
KPDSupply("note-case", 22, 80, 1),
KPDSupply("sunglasses", 7, 20, 1),
KPDSupply("towel", 18, 12, 2),
KPDSupply("socks", 4, 50, 1),
KPDSupply("book", 30, 10, 2)]
pack = solve(gear, 400)
println("The hiker should pack: \n - ", join(pack, "\n - "))
println("\nPacked weight: ", sum(getfield.(pack, :weight)), " kg")
println("Packed value: ", sum(getfield.(pack, :value)), " €")
- Output:
The hiker should pack: - 1 map (9 kg, 150 €) - 1 compass (13 kg, 35 €) - 1 water (153 kg, 200 €) - 2 glucose (15 kg, 60 €) - 3 banana (27 kg, 60 €) - 1 cheese (23 kg, 30 €) - 1 suntan cream (11 kg, 70 €) - 1 waterproof overclothes (43 kg, 75 €) - 1 note-case (22 kg, 80 €) - 1 sunglasses (7 kg, 20 €) - 1 socks (4 kg, 50 €) Packed weight: 327 kg Packed value: 830 €
Kotlin
// version 1.1.2
data class Item(val name: String, val weight: Int, val value: Int, val count: Int)
val items = listOf(
Item("map", 9, 150, 1),
Item("compass", 13, 35, 1),
Item("water", 153, 200, 2),
Item("sandwich", 50, 60, 2),
Item("glucose", 15, 60, 2),
Item("tin", 68, 45, 3),
Item("banana", 27, 60, 3),
Item("apple", 39, 40, 3),
Item("cheese", 23, 30, 1),
Item("beer", 52, 10, 3),
Item("suntan cream", 11, 70, 1),
Item("camera", 32, 30, 1),
Item("T-shirt", 24, 15, 2),
Item("trousers", 48, 10, 2),
Item("umbrella", 73, 40, 1),
Item("waterproof trousers", 42, 70, 1),
Item("waterproof overclothes", 43, 75, 1),
Item("note-case", 22, 80, 1),
Item("sunglasses", 7, 20, 1),
Item("towel", 18, 12, 2),
Item("socks", 4, 50, 1),
Item("book", 30, 10, 2)
)
val n = items.size
const val MAX_WEIGHT = 400
fun knapsack(w: Int): IntArray {
val m = Array(n + 1) { IntArray(w + 1) }
for (i in 1..n) {
for (j in 0..w) {
m[i][j] = m[i - 1][j]
for (k in 1..items[i - 1].count) {
if (k * items[i - 1].weight > j) break
val v = m[i - 1][j - k * items[i - 1].weight] + k * items[i - 1].value
if (v > m[i][j]) m[i][j] = v
}
}
}
val s = IntArray(n)
var j = w
for (i in n downTo 1) {
val v = m[i][j]
var k = 0
while (v != m[i - 1][j] + k * items[i - 1].value) {
s[i - 1]++
j -= items[i - 1].weight
k++
}
}
return s
}
fun main(args: Array<String>) {
val s = knapsack(MAX_WEIGHT)
println("Item Chosen Weight Value Number")
println("--------------------- ------ ----- ------")
var itemCount = 0
var sumWeight = 0
var sumValue = 0
var sumNumber = 0
for (i in 0 until n) {
if (s[i] == 0) continue
itemCount++
val name = items[i].name
val number = s[i]
val weight = items[i].weight * number
val value = items[i].value * number
sumNumber += number
sumWeight += weight
sumValue += value
println("${name.padEnd(22)} ${"%3d".format(weight)} ${"%4d".format(value)} ${"%2d".format(number)}")
}
println("--------------------- ------ ----- ------")
println("Items chosen $itemCount ${"%3d".format(sumWeight)} ${"%4d".format(sumValue)} ${"%2d".format(sumNumber)}")
}
- Output:
Item Chosen Weight Value Number --------------------- ------ ----- ------ map 9 150 1 compass 13 35 1 water 153 200 1 glucose 30 120 2 banana 81 180 3 cheese 23 30 1 suntan cream 11 70 1 waterproof overclothes 43 75 1 note-case 22 80 1 sunglasses 7 20 1 socks 4 50 1 --------------------- ------ ----- ------ Items chosen 11 396 1010 14
Mathematica /Wolfram Language
Transpose@{#[[;; , 1]],
LinearProgramming[-#[[;; , 3]], -{#[[;; , 2]]}, -{400},
{0, #[[4]]} & /@ #, Integers]} &@{{"map", 9, 150, 1},
{"compass", 13, 35, 1},
{"water", 153, 200, 2},
{"sandwich", 50, 60, 2},
{"glucose", 15, 60, 2},
{"tin", 68, 45, 3},
{"banana", 27, 60, 3},
{"apple", 39, 40, 3},
{"cheese", 23, 30, 1},
{"beer", 52, 10, 3},
{"suntan cream", 11, 70, 1},
{"camera", 32, 30, 1},
{"T-shirt", 24, 15, 2},
{"trousers", 48, 10, 2},
{"umbrella", 73, 40, 1},
{"waterproof trousers", 42, 70, 1},
{"waterproof overclothes", 43, 75, 1},
{"note-case", 22, 80, 1},
{"sunglasses", 7, 20, 1},
{"towel", 18, 12, 2},
{"socks", 4, 50, 1},
{"book", 30, 10, 2}}
- Output:
{{"map", 1}, {"compass", 1}, {"water", 1}, {"sandwich",
0}, {"glucose", 2}, {"tin", 0}, {"banana", 3}, {"apple",
0}, {"cheese", 1}, {"beer", 0}, {"suntan cream", 1}, {"camera",
0}, {"T-shirt", 0}, {"trousers", 0}, {"umbrella",
0}, {"waterproof trousers", 0}, {"waterproof overclothes",
1}, {"note-case", 1}, {"sunglasses", 1}, {"towel", 0}, {"socks",
1}, {"book", 0}}
Mathprog
/*Knapsack
This model finds the integer optimal packing of a knapsack
Nigel_Galloway
January 9th., 2012
*/
set Items;
param weight{t in Items};
param value{t in Items};
param quantity{t in Items};
var take{t in Items}, integer, >=0, <=quantity[t];
knap_weight : sum{t in Items} take[t] * weight[t] <= 400;
maximize knap_value: sum{t in Items} take[t] * value[t];
data;
param : Items : weight value quantity :=
map 9 150 1
compass 13 35 1
water 153 200 2
sandwich 50 60 2
glucose 15 60 2
tin 68 45 3
banana 27 60 3
apple 39 40 3
cheese 23 30 1
beer 52 10 3
suntancream 11 70 1
camera 32 30 1
T-shirt 24 15 2
trousers 48 10 2
umbrella 73 40 1
w-trousers 42 70 1
w-overclothes 43 75 1
note-case 22 80 1
sunglasses 7 20 1
towel 18 12 2
socks 4 50 1
book 30 10 2
;
end;The solution produced using glpk is here: Knapsack problem/Bounded/Mathprog
lpsolve may also be used. The result may be found here: File:Knap_objective.png
The constraints may be found here: File:Knap_constraint.png
MiniZinc
%Solve Knapsack Problem Bounded. Nigel Galloway, Octoer 12th., 2020.
enum Items={map,compass,water,sandwich,glucose,tin,banana,apple,cheese,beer,suntan_cream,camera,t_shirt,trousers,umbrella,waterproof_trousers,waterproof_overclothes,note_case,sunglasses,towel,socks,book};
array[Items] of int: weight =[9,13,153,50,15,68,27,39,23,52,11,32,24,48,73,42,43,22,7,18,4,30];
array[Items] of int: value =[150,35,200,60,60,45,60,40,30,10,70,30,15,10,40,70,75,80,20,12,50,10];
array[Items] of int: quantity=[1,1,2,2,2,3,3,3,1,3,1,1,2,2,1,1,1,1,1,2,1,2];
array[Items] of var 0..max(quantity): take; constraint forall(n in Items)(take[n]<=quantity[n]);
int: maxWeight=400;
var int: wTaken=sum(n in Items)(weight[n]*take[n]);
var int: wValue=sum(n in Items)(value[n]*take[n]);
constraint wTaken <= maxWeight;
solve maximize wValue;
output[concat([let {string: g=show(take[n])} in "Take "++(if g==show(quantity[n]) then "all" else g endif)++" of \(n)\n" | n in Items where show(take[n])!="0"])++"\nTotal Weight=\(wTaken) Total Value="++show_float(4,2,wValue)]- Output:
Take all of map Take all of compass Take 1 of water Take all of glucose Take all of banana Take all of cheese Take all of suntan_cream Take all of waterproof_overclothes Take all of note_case Take all of sunglasses Take all of socks Total Weight=396 Total Value=1010.00
Nim
We expand the list of items and apply the 0-1 algorithm.
# Knapsack. Recursive solution.
import strformat
import tables
# Description of an item.
type Item = tuple[name: string; weight, value, pieces: int]
# List of available items.
const Items: seq[Item] = @[("map", 9, 150, 1),
("compass", 13, 35, 1),
("water", 153, 200, 2),
("sandwich", 50, 60, 2),
("glucose", 15, 60, 2),
("tin", 68, 45, 3),
("banana", 27, 60, 3),
("apple", 39, 40, 3),
("cheese", 23, 30, 1),
("beer", 52, 10, 3),
("suntan cream", 11, 70, 1),
("camera", 32, 30, 1),
("T-shirt", 24, 15, 2),
("trousers", 48, 10, 2),
("umbrella", 73, 40, 1),
("waterproof trousers", 42, 70, 1),
("waterproof overclothes", 43, 75, 1),
("note-case", 22, 80, 1),
("sunglasses", 7, 20, 1),
("towel", 18, 12, 2),
("socks", 4, 50, 1),
("book", 30, 10, 2)
]
type
# Item numbers (used rather than items themselves).
Number = range[0..Items.high]
# Description of an expanded item.
ExpandedItem = tuple[num: Number; weight, value: int]
# Expanded items management.
proc expandedItems(items: seq[Item]): seq[ExpandedItem] =
## Expand the list of items.
for idx, item in Items:
for _ in 1..item.pieces:
result.add((idx.Number, item.weight, item.value))
const ItemList = expandedItems(Items)
type
# Index in the expanded list.
ExpandedIndex = 0..ItemList.high
# Chosen items and their total value.
Choice = tuple[indexes: set[ExpandedIndex]; weight, value: int]
# Cache used to speed up the search.
var cache: Table[tuple[index, weight: int], Choice]
#---------------------------------------------------------------------------------------------------
proc select(idx, weightLimit: int): Choice =
## Find the best choice starting from item at index "idx".
if idx < 0 or weightLimit == 0:
return
if (idx, weightLimit) in cache:
return cache[(idx, weightLimit)]
let weight = ItemList[idx].weight
if weight > weightLimit:
return select(idx - 1, weightLimit)
# Try by leaving this item and selecting among remaining items.
result = select(idx - 1, weightLimit)
# Try by taking this item and completing with some remaining items.
var result1 = select(idx - 1, weightLimit - weight)
inc result1.value, ItemList[idx].value
# Select the best choice (giving the greater value).
if result1.value > result.value:
result = (result1.indexes + {idx.ExpandedIndex}, result1.weight + weight, result1.value)
cache[(idx, weightLimit)] = result
#---------------------------------------------------------------------------------------------------
let (indexes, weight, value) = select(ItemList.high, 400)
# Count the number of pieces for each item.
var pieces = newSeq[int](Items.len)
for idx in indexes:
inc pieces[ItemList[idx].num]
echo "List of items:"
for num in 0..Items.high:
if pieces[num] > 0:
echo fmt"– {pieces[num]} of {Items[num].pieces} {Items[num].name}"
echo ""
echo "Total weight: ", weight
echo "Total value: ", value
- Output:
List of items: – 1 of 1 map – 1 of 1 compass – 1 of 2 water – 2 of 2 glucose – 3 of 3 banana – 1 of 1 cheese – 1 of 1 suntan cream – 1 of 1 waterproof overclothes – 1 of 1 note-case – 1 of 1 sunglasses – 1 of 1 socks Total weight: 396 Total value: 1010
OOCalc
OpenOffice.org Calc has (several) linear solvers. To solve this task, first copy in the table from the task description, then add the extra columns:
- Number: (How many chosen)
- weight of n
- value of n
Add a TOTALS row to sum the weight/value of n.
The sheet should then look like this:
table pre solving
Open the "Tools->Solver..." menu item and fill in the following items:
- Target Cell: $H$27
- Optimise result to: maximum
- By Changing cells: $F$5:$F$26
- Limiting conditions:
- $F$5:$F$26 <= $E$5:$E$26
- $G$27 <= 400
solver menu
- Options... (opens a separate popup window, then continue)
- Solver engine: OpenOffice.org Linear Solver
- Settings:
- Assume variables as integer: True
- Assume variables as non-negative: True
- Epsilon level: 0
- Limit branch-and-bound depth: True
- Solving time limit (seconds): 100
solver popup options menu
OK the solver options window leaving the Solver window open, then select solve to produce in seconds:
Table solved
OxygenBasic
type KnapSackItem string name,sys dag,value,tag
KnapSackItem it[100]
sys dmax=400
sys items=22
it=>
"map", 9, 150, 0,
"compass", 13, 35, 0,
"water", 153, 200, 0,
"sandwich", 50, 160, 0,
"glucose", 15, 60, 0,
"tin", 68, 45, 0,
"banana", 27, 60, 0,
"apple", 39, 40, 0,
"cheese", 23, 30, 0,
"beer", 52, 10, 0,
"suntan cream", 11, 70, 0,
"camera", 32, 30, 0,
"T-shirt", 24, 15, 0,
"trousers", 48, 10, 0,
"umbrella", 73, 40, 0,
"waterproof trousers", 42, 70, 0,
"waterproof overclothes",43, 75, 0,
"note-case", 22, 80, 0,
"sunglasses", 7, 20, 0,
"towel", 18, 12, 0,
"socks", 4, 50, 0,
"book", 30, 10, 0
tot=0
for i=1 to items
tot+=it(i).dag
next
xs=tot-dmax
'REMOVE LOWEST PRIORITY ITEMS TILL XS<=0
cr=chr(13)+chr(10)
tab=chr(9)
pr="remove: " cr
c=0
do
v=1e9
w=0
k=0
'
'FIND NEXT LEAST VALUE ITEM
'
for i=1 to items
if it[i].tag=0
'w=it[i].value 'TEST PRIORITY ONLY
w=1000*it[i].value/it[i].dag 'TEST PRIORIT/WEIGHT VALUE
if w<v then v=w : k=i
end if
next
'
'LOG AND REMOVE FROM LIST
'
if k
xs-=it[k].dag 'deduct from excess weight
it[k].tag=1
pr+=it(k).name tab it(k).dag tab it(k).value cr
if xs<=0 then exit do 'Weight within dmax
end if
c++
if c>=items then exit do
end do
'
pr+=cr "Knapsack contents: " cr
'
for i=1 to items
if it(i).tag=0
pr+=it(i).name tab it(i).dag tab it(i).value cr
end if
next
'TRY FITTING IN LOWER PRIORITY ITEMS
av=-xs
for i=1 to items
if it[i].tag
if av-it[i].dag > 0 then
pr+="Can include: " it(i).name tab it(i).dag tab it(i).value cr
av-=it[i].dag
end if
end if
next
pr+=cr "Weight: " dmax+xs
'putfile "s.txt",pr
print pr
'Knapsack contents:
'map 9 150
'compass 13 35
'water 153 200
'sandwich 50 160
'glucose 15 60
'banana 27 60
'suntan cream 11 70
'waterproof trousers 42 70
'waterproof overclothes 43 75
'note-case 22 80
'sunglasses 7 20
'socks 4 50
'
'Weight: 396Oz
Using constraint programming.
declare
%% maps items to tuples of
%% Weight(hectogram), Value and available Pieces
Problem = knapsack('map':9#150#1
'compass':13#35#1
'water':153#200#2
'sandwich':50#60#2
'glucose':15#60#2
'tin':68#45#3
'banana':27#60#3
'apple':39#40#3
'cheese':23#30#1
'beer':52#10#3
'suntan cream':11#70#1
'camera':32#30#1
't-shirt':24#15#2
'trousers':48#10#2
'umbrella':73#40#1
'waterproof trousers':42#70#1
'waterproof overclothes':43#75#1
'note-case':22#80#1
'sunglasses':7#20#1
'towel':18#12#2
'socks':4#50#1
'book':30#10#2
)
%% item -> Weight
Weights = {Record.map Problem fun {$ X} X.1 end}
%% item -> Value
Values = {Record.map Problem fun {$ X} X.2 end}
proc {Knapsack Solution}
%% a solution maps items to finite domain variables
%% whose maximum values depend on the item type
Solution = {Record.map Problem fun {$ _#_#Max} {FD.int 0#Max} end}
%% no more than 400 hectograms
{FD.sumC Weights Solution '=<:' 400}
%% search through valid solutions
{FD.distribute naive Solution}
end
proc {PropagateLargerValue Old New}
%% propagate that new solutions must yield a higher value
%% than previously found solutions (essential for performance)
{FD.sumC Values New '>:' {Value Old}}
end
fun {Value Candidate}
{Record.foldL {Record.zip Candidate Values Number.'*'} Number.'+' 0}
end
fun {Weight Candidate}
{Record.foldL {Record.zip Candidate Weights Number.'*'} Number.'+' 0}
end
[Best] = {SearchBest Knapsack PropagateLargerValue}
in
{System.showInfo "Items: "}
{Record.forAllInd Best
proc {$ I V}
if V > 0 then
{System.showInfo I#": "#V}
end
end
}
{System.printInfo "\n"}
{System.showInfo "total value: "#{Value Best}}
{System.showInfo "total weight: "#{Weight Best}}- Output:
Items: banana: 3 cheese: 1 compass: 1 glucose: 2 map: 1 note-case: 1 socks: 1 sunglasses: 1 suntan cream: 1 water: 1 waterproof overclothes: 1 total value: 1010 total weight: 396
Takes about 3 seconds on a slow netbook.
Pascal
Dynamic programming solution (tested with FPC 3.2.2).
program KnapsackBounded;
{$mode objfpc}{$j-}
uses
SysUtils, Math;
type
TItem = record
Name: string;
Weight, Value, Count: Integer;
end;
const
NUM_ITEMS = 22;
ITEMS: array[0..NUM_ITEMS-1] of TItem = (
(Name: 'map'; Weight: 9; Value: 150; Count: 1),
(Name: 'compass'; Weight: 13; Value: 35; Count: 1),
(Name: 'water'; Weight: 153; Value: 200; Count: 2),
(Name: 'sandwich'; Weight: 50; Value: 60; Count: 2),
(Name: 'glucose'; Weight: 15; Value: 60; Count: 2),
(Name: 'tin'; Weight: 68; Value: 45; Count: 3),
(Name: 'banana'; Weight: 27; Value: 60; Count: 3),
(Name: 'apple'; Weight: 39; Value: 40; Count: 3),
(Name: 'cheese'; Weight: 23; Value: 30; Count: 1),
(Name: 'beer'; Weight: 52; Value: 10; Count: 3),
(Name: 'suntan cream'; Weight: 11; Value: 70; Count: 1),
(Name: 'camera'; Weight: 32; Value: 30; Count: 1),
(Name: 'T-shirt'; Weight: 24; Value: 15; Count: 2),
(Name: 'trousers'; Weight: 48; Value: 10; Count: 2),
(Name: 'umbrella'; Weight: 73; Value: 40; Count: 1),
(Name: 'waterproof trousers'; Weight: 42; Value: 70; Count: 1),
(Name: 'waterproof overclothes'; Weight: 43; Value: 75; Count: 1),
(Name: 'note-case'; Weight: 22; Value: 80; Count: 1),
(Name: 'sunglasses'; Weight: 7; Value: 20; Count: 1),
(Name: 'towel'; Weight: 18; Value: 12; Count: 2),
(Name: 'socks'; Weight: 4; Value: 50; Count: 1),
(Name: 'book'; Weight: 30; Value: 10; Count: 2)
);
MAX_WEIGHT = 400;
var
D: array of array of Integer; //DP matrix
I, W, V, C, MaxWeight: Integer;
begin
SetLength(D, NUM_ITEMS + 1, MAX_WEIGHT + 1);
for I := 0 to High(ITEMS) do
for W := 0 to MAX_WEIGHT do begin
D[I+1, W] := D[I, W];
for C := 1 to ITEMS[I].Count do begin
if ITEMS[I].Weight * C > W then break;
V := D[I, W - ITEMS[I].Weight * C] + ITEMS[I].Value * C;
if V > D[I+1, W] then
D[I+1, W] := V;
end;
end;
W := MAX_WEIGHT;
MaxWeight := 0;
WriteLn('bagged:');
for I := High(ITEMS) downto 0 do begin
V := D[I+1, W];
C := 0;
while V <> D[I, W] + ITEMS[I].Value * C do begin
Dec(W, ITEMS[I].Weight);
Inc(C);
end;
Inc(MaxWeight, C * ITEMS[I].Weight);
if C <> 0 then
WriteLn(' ', C, ' ', ITEMS[I].Name);
end;
WriteLn('value = ', D[NUM_ITEMS, MAX_WEIGHT]);
WriteLn('weight = ', MaxWeight);
end.
- Output:
bagged: 1 socks 1 sunglasses 1 note-case 1 waterproof overclothes 1 suntan cream 1 cheese 3 banana 2 glucose 1 water 1 compass 1 map value = 1010 weight = 396
Perl
Recursive solution with caching.
#!/usr/bin/perl
use strict;
my $raw = <<'TABLE';
map 9 150 1
compass 13 35 1
water 153 200 2
sandwich 50 60 2
glucose 15 60 2
tin 68 45 3
banana 27 60 3
apple 39 40 3
cheese 23 30 1
beer 52 10 1
suntancream 11 70 1
camera 32 30 1
T-shirt 24 15 2
trousers 48 10 2
umbrella 73 40 1
w_trousers 42 70 1
w_overcoat 43 75 1
note-case 22 80 1
sunglasses 7 20 1
towel 18 12 2
socks 4 50 1
book 30 10 2
TABLE
my @items;
for (split "\n", $raw) {
my @x = split /\s+/;
push @items, {
name => $x[0],
weight => $x[1],
value => $x[2],
quant => $x[3],
}
}
my $max_weight = 400;
my %cache;
sub pick {
my ($weight, $pos) = @_;
if ($pos < 0 or $weight <= 0) {
return 0, 0, []
}
@{ $cache{$weight, $pos} //= [do{ # odd construct: for caching
my $item = $items[$pos];
my ($bv, $bi, $bw, $bp) = (0, 0, 0, []);
for my $i (0 .. $item->{quant}) {
last if $i * $item->{weight} > $weight;
my ($v, $w, $p) = pick($weight - $i * $item->{weight}, $pos - 1);
next if ($v += $i * $item->{value}) <= $bv;
($bv, $bi, $bw, $bp) = ($v, $i, $w, $p);
}
my @picked = ( @$bp, $bi );
$bv, $bw + $bi * $item->{weight}, \@picked
}]}
}
my ($v, $w, $p) = pick($max_weight, $#items);
for (0 .. $#$p) {
if ($p->[$_] > 0) {
print "$p->[$_] of $items[$_]{name}\n";
}
}
print "Value: $v; Weight: $w\n";
- Output:
1 of map 1 of compass 1 of water 2 of glucose 3 of banana 1 of cheese 1 of suntancream 1 of w_overcoat 1 of note-case 1 of sunglasses 1 of socks Value: 1010; Weight: 396
Phix
Very dumb and very slow brute force version
Of no practical use, except for comparison against improvements.
with javascript_semantics atom t0 = time() constant goodies = { -- item weight value pieces {"map", 9, 150, 1}, {"compass", 13, 35, 1}, {"sandwich", 50, 60, 2}, {"glucose", 15, 60, 2}, {"tin", 68, 45, 3}, {"banana", 27, 60, 3}, {"apple", 39, 40, 3}, {"cheese", 23, 30, 1}, {"beer", 52, 10, 3}, {"suntan cream", 11, 70, 1}, {"water", 153, 200, 2}, {"camera", 32, 30, 1}, {"T-shirt", 24, 15, 2}, {"trousers", 48, 10, 2}, {"umbrella", 73, 40, 1}, {"waterproof trousers", 42, 70, 1}, {"waterproof overclothes", 43, 75, 1}, {"note-case", 22, 80, 1}, {"sunglasses", 7, 20, 1}, {"towel", 18, 12, 2}, {"socks", 4, 50, 1}, {"book", 30, 10, 2}} function knapsack(integer max_weight, integer at) integer best_points = 0, points sequence best_choices = {}, choices atom act_weight = 0, sub_weight if at>=1 then integer {?,witem,pitem,imax} = goodies[at] for i=0 to imax do integer wlim = max_weight-i*witem if wlim<0 then exit end if {points,sub_weight,choices} = knapsack(wlim, at-1) points += i*pitem if points>best_points then best_points = points best_choices = deep_copy(choices)&i act_weight = sub_weight+i*witem end if end for end if return {best_points, act_weight, best_choices} end function sequence res = knapsack(400, length(goodies)) -- {points,act_weight,choices} atom weight = 0, witem atom points = 0, pitem string idesc for i=1 to length(goodies) do integer c = res[3][i] if c then {idesc,witem,pitem} = goodies[i] printf(1,"%d %s\n",{c,idesc}) weight += c*witem points += c*pitem end if end for if points!=res[1] then ?9/0 end if -- sanity check printf(1,"Value %d, weight %g [%3.2fs]\n",{points,weight,time()-t0})
- Output:
1 map 1 compass 2 glucose 3 banana 1 cheese 1 suntan cream 1 water 1 waterproof overclothes 1 note-case 1 sunglasses 1 socks Value 1010, weight 396 [17.53s]
Dynamic Programming version
Much faster but limited to integer weights
with javascript_semantics sequence items = { {"map", 9, 150, 1}, {"compass", 13, 35, 1}, {"water", 153, 200, 2}, {"sandwich", 50, 60, 2}, {"glucose", 15, 60, 2}, {"tin", 68, 45, 3}, {"banana", 27, 60, 3}, {"apple", 39, 40, 3}, {"cheese", 23, 30, 1}, {"beer", 52, 10, 3}, {"suntan cream", 11, 70, 1}, {"camera", 32, 30, 1}, {"T-shirt", 24, 15, 2}, {"trousers", 48, 10, 2}, {"umbrella", 73, 40, 1}, {"waterproof trousers", 42, 70, 1}, {"waterproof overclothes",43, 75, 1}, {"note-case", 22, 80, 1}, {"sunglasses", 7, 20, 1}, {"towel", 18, 12, 2}, {"socks", 4, 50, 1}, {"book", 30, 10, 2}, }; sequence {names,weights,points,counts} = columnize(items) constant n = length(items) function knapsack(int w) integer v -- m is the achievable points matrix: -- Note that Phix uses 1-based indexes, so m[1][1] -- actually holds points for 0 items of weight 0, -- and m[n+1][w+1] is for n items at weight w. sequence m = repeat(repeat(0,w+1),n+1) for i=1 to n do for j=1 to w+1 do -- (0 to w really) m[i+1][j] = m[i][j] for k=1 to counts[i] do if k*weights[i]>j-1 then exit end if v = m[i][j-k*weights[i]]+k*points[i] if v>m[i+1][j] then m[i+1][j] = v end if end for end for end for sequence s = repeat(0,n) integer j = w+1 -- (w -> 0 really) for i=n to 1 by -1 do v = m[i+1][j] integer k = 0 while v!=m[i][j]+k*points[i] do s[i] += 1 j -= weights[i] k += 1 end while end for return s end function integer tc = 0, tw = 0, tv = 0 sequence s = knapsack(400) for i=1 to n do integer si = s[i] if si then printf(1,"%-22s %5d %5d %5d\n", {names[i], si, si*weights[i], si*points[i]}) tc += si tw += si*weights[i] tv += si*points[i] end if end for printf(1,"%-22s %5d %5d %5d\n", {"count, weight, points:", tc, tw, tv})
- Output:
map 1 9 150 compass 1 13 35 water 1 153 200 glucose 2 30 120 banana 3 81 180 cheese 1 23 30 suntan cream 1 11 70 waterproof overclothes 1 43 75 note-case 1 22 80 sunglasses 1 7 20 socks 1 4 50 count, weight, points: 14 396 1010
Range cache version
The main problem with the dynamic programming solution is that it is only practical for integer weights. You could multiply by 1000 and truncate to get an approximation to the nearest 0.001kg, but the memory use would obviously increase dramatically. A naive cache could also suffer similarly, if it retained duplicate solutions for w=15.783, 15.784, 15.785, and everything in between. Using a (bespoke) range cache solves this problem, although the simplistic version given could probably be improved with a binary search or similar. It also significantly reduces the workload; for instance if you find a solution for 170 that actually weighs 150 then any subsequent query in 150..170 requires zero work, unlike the naive cache and dp solutions.
-- demo\rosetta\knapsackB.exw with javascript_semantics atom t0 = time() enum HI,PTS,ACTW,SOLN sequence range_cache = {} integer cache_entries = 0 procedure add_range(integer at, atom weight, atom actual_weight, atom points, sequence soln) assert(actual_weight<=weight) for i=length(range_cache)+1 to at do -- (while too small do) if i=at then range_cache = append(range_cache,{{weight,points,actual_weight,soln}}) cache_entries += 1 return end if range_cache = append(range_cache,{}) end for integer lastHI = -1 for i=1 to length(range_cache[at]) do sequence rcati = range_cache[at][i] if weight=rcati[ACTW] then assert(rcati[PTS..SOLN]=={points,actual_weight,soln}) return elsif weight<rcati[ACTW] then -- (we cannot extend an existing range down...) assert(soln!=rcati[SOLN]) -- insert a new range range_cache[at][i..i-1] = {{weight,points,actual_weight,soln}} cache_entries += 1 return elsif soln=rcati[SOLN] then assert(rcati[PTS..SOLN]=={points,actual_weight,soln}) if weight>rcati[HI] then -- extend existing range up rcati = {} range_cache[at][i][HI] = weight end if return elsif weight<=rcati[HI] then crash("duplicate solution??") -- (or discard as below) -- return -- (discard) end if assert(rcati[ACTW]>lastHI) lastHI = rcati[HI] end for range_cache[at] = append(range_cache[at],{weight,points,actual_weight,soln}) cache_entries += 1 end procedure function in_range(integer at, atom weight) if at<=length(range_cache) then for i=1 to length(range_cache[at]) do sequence rcati = range_cache[at][i] if weight<=rcati[HI] then if weight>=rcati[ACTW] then return rcati[PTS..SOLN] -- {pts,act_weight,soln} end if exit end if end for end if return {} -- (no suitable cache entry found) end function sequence goodies = ({ -- item weight value pieces {"map", 9, 150, 1}, {"compass", 13, 35, 1}, {"sandwich", 50, 60, 2}, {"glucose", 15, 60, 2}, {"tin", 68, 45, 3}, {"banana", 27, 60, 3}, {"apple", 39, 40, 3}, {"cheese", 23, 30, 1}, {"beer", 52, 10, 3}, {"suntan cream", 11, 70, 1}, {"water", 153, 200, 2}, {"camera", 32, 30, 1}, {"T-shirt", 24, 15, 2}, {"trousers", 48, 10, 2}, {"umbrella", 73, 40, 1}, {"waterproof trousers", 42, 70, 1}, {"waterproof overclothes", 43, 75, 1}, {"note-case", 22, 80, 1}, {"sunglasses", 7, 20, 1}, {"towel", 18, 12, 2}, {"socks", 4, 50, 1}, {"book", 30, 10, 2}}) integer cache_hits = 0 integer cache_misses = 0 function knapsack(integer max_weight, integer at) integer best_points = 0, points sequence best_choices = {}, choices atom act_weight = 0, sub_weight if at>=1 then sequence soln = in_range(at,max_weight) if length(soln) then cache_hits += 1 return soln end if cache_misses += 1 integer {?,witem,pitem,imax} = goodies[at] best_choices = repeat(0,at) for i=0 to imax do integer wlim = max_weight-i*witem if wlim<0 then exit end if {points,sub_weight,choices} = knapsack(wlim, at-1) points += i*pitem if points>best_points then best_points = points best_choices = deep_copy(choices)&i act_weight = sub_weight+i*witem end if end for add_range(at,max_weight,act_weight,best_points,best_choices) end if return {best_points, act_weight, best_choices} end function sequence res = knapsack(400, length(goodies)) -- {points,act_weight,choices} atom weight = 0, witem atom points = 0, pitem string idesc sequence choices = res[3] for i=1 to length(goodies) do integer c = choices[i] if c then {idesc,witem,pitem} = goodies[i] printf(1,"%d %s\n",{c,idesc}) weight += c*witem points += c*pitem end if end for assert({points,weight}==res[1..2]) -- sanity check printf(1,"Value %d, weight %g [%3.2fs]:\n",{points,weight,time()-t0}) printf(1,"cache_entries:%d, hits:%d, misses:%d\n",{cache_entries,cache_hits,cache_misses})
- Output:
1 map 1 compass 2 glucose 3 banana 1 cheese 1 suntan cream 1 water 1 waterproof overclothes 1 note-case 1 sunglasses 1 socks Value 1010, weight 396 [0.00s] cache_entries:409, hits:1226, misses:882
The distributed version contains additional comments and extra code for comparing this against a naive cache and no cache (CACHE_RANGE shown above).
CACHE_SIMPLE: (as above but ending)
Value 1010, weight 396 [0.08s] cache_entries:5549, hits:7707, misses:5549
Even on this simple integer-only case, range cache reduces cache size better than 10-fold and effort 6-fold.
We also know the dp solution matrix has 9223 entries, admittedly each being much smaller than a cache entry.
And finally CACHE_NONE (the dumb version): (as above but ending)
Value 1010, weight 396 [18.14s] cache_entries:0, hits:0, misses:33615741
Picat
import mip,util.
go =>
data(AllItems,MaxWeight),
[Items,Weights,Values,Pieces] = transpose(AllItems),
knapsack_bounded(Weights,Values,Pieces,MaxWeight, X,TotalWeight,TotalValue),
print_solution(Items,Weights,Values, X,TotalWeight,TotalValue),
nl.
% Print the solution
print_solution(Items,Weights,Values, X,TotalWeight,TotalValue) ?=>
println("\nThese are the items to pick:"),
println(" Item Weight Value"),
foreach(I in 1..Items.len)
if X[I] > 0 then
printf("* %d %-29w %3d %3d\n", X[I],Items[I],Weights[I],Values[I])
end
end,
nl,
printf("Total weight: %d\n", TotalWeight),
printf("Total value: %d\n", TotalValue),
nl.
% Solve knapsack problem
knapsack_bounded(Weights,Values,Pieces,MaxWeight, X,TotalWeight,TotalValue) =>
NumItems = length(Weights),
% Variables
MaxPieces = max(Pieces),
X = new_list(NumItems),
X :: 0..MaxPieces,
% Constraints
SumValues = sum(Values),
TotalValue :: 0..SumValues,
TotalWeight :: 0..MaxWeight,
scalar_product(Weights,X,TotalWeight),
scalar_product(Values,X,TotalValue),
TotalWeight #<= MaxWeight,
% Check number of pieces
foreach({XVal,Piece} in zip(X,Pieces))
XVal #=< Piece
end,
% Search
Vars = X ++ [TotalWeight, TotalValue],
solve($[max(TotalValue),down],Vars).
% data
data(Items,MaxWeight) =>
Items =
% Item Weight Value Pieces
[["map", 9, 150, 1],
["compass", 13, 35, 1],
["water", 153, 200, 2],
["sandwich", 50, 60, 2],
["glucose", 15, 60, 2],
["tin", 68, 45, 3],
["banana", 27, 60, 3],
["apple", 39, 40, 3],
["cheese", 23, 30, 1],
["beer", 52, 10, 3],
["suntancream", 11, 70, 1],
["camera", 32, 30, 1],
["T-shirt", 24, 15, 2],
["trousers", 48, 10, 2],
["umbrella", 73, 40, 1],
["waterproof trousers", 42, 70, 1],
["waterproof overclothes", 43, 75, 1],
["note-case", 22, 80, 1],
["sunglasses", 7, 20, 1],
["towel", 18, 12, 2],
["socks", 4, 50, 1],
["book", 30, 10, 2]],
MaxWeight = 400.- Output:
These are the items to pick: Item Weight Value * 1 map 9 150 * 1 compass 13 35 * 1 water 153 200 * 2 glucose 15 60 * 3 banana 27 60 * 1 cheese 23 30 * 1 suntancream 11 70 * 1 waterproof overclothes 43 75 * 1 note-case 22 80 * 1 sunglasses 7 20 * 1 socks 4 50 Total weight: 396 Total value: 1010
PicoLisp
(de *Items
("map" 9 150 1) ("compass" 13 35 1)
("water" 153 200 3) ("sandwich" 50 60 2)
("glucose" 15 60 2) ("tin" 68 45 3)
("banana" 27 60 3) ("apple" 39 40 3)
("cheese" 23 30 1) ("beer" 52 10 3)
("suntan cream" 11 70 1) ("camera" 32 30 1)
("t-shirt" 24 15 2) ("trousers" 48 10 2)
("umbrella" 73 40 1) ("waterproof trousers" 42 70 1)
("waterproof overclothes" 43 75 1) ("note-case" 22 80 1)
("sunglasses" 7 20 1) ("towel" 18 12 2)
("socks" 4 50 1) ("book" 30 10 2) )
# Dynamic programming solution
(de knapsack (Lst W)
(when Lst
(cache '*KnapCache (cons W Lst)
(let X (knapsack (cdr Lst) W)
(if (ge0 (- W (cadar Lst)))
(let Y (cons (car Lst) (knapsack (cdr Lst) @))
(if (> (sum caddr X) (sum caddr Y)) X Y) )
X ) ) ) ) )
(let K
(knapsack
(mapcan # Expand multiple items
'((X) (need (cadddr X) NIL X))
*Items )
400 )
(for I K
(apply tab I (3 -24 6 6) NIL) )
(tab (27 6 6) NIL (sum cadr K) (sum caddr K)) )- Output:
map 9 150
compass 13 35
water 153 200
glucose 15 60
glucose 15 60
banana 27 60
banana 27 60
banana 27 60
cheese 23 30
suntan cream 11 70
waterproof overclothes 43 75
note-case 22 80
sunglasses 7 20
socks 4 50
396 1010
Prolog
Library clpfd
Library clpfd is written by Markus Triska. Takes about 3 seconds to compute the best solution.
:- use_module(library(clpfd)).
% tuples (name, weights, value, nb pieces).
knapsack :-
L = [( map, 9, 150, 1),
( compass, 13, 35, 1),
( water, 153, 200, 2),
( sandwich, 50, 60, 2),
( glucose, 15, 60, 2),
( tin, 68, 45, 3),
( banana, 27, 60, 3),
( apple, 39, 40, 3),
( cheese, 23, 30, 1),
( beer, 52, 10, 3),
( 'suntan cream', 11, 70, 1),
( camera, 32, 30, 1),
( 'T-shirt', 24, 15, 2),
( trousers, 48, 10, 2),
( umbrella, 73, 40, 1),
( 'waterproof trousers', 42, 70, 1),
( 'waterproof overclothes', 43, 75, 1),
( 'note-case', 22, 80, 1),
( sunglasses, 7, 20, 1),
( towel, 18, 12, 2),
( socks, 4, 50, 1),
( book, 30, 10, 2)],
% Takes is the list of the numbers of each items
% these numbers are between 0 and the 4th value of the tuples of the items
maplist(collect, L, Ws, Vs, Takes),
scalar_product(Ws, Takes, #=<, 400),
scalar_product(Vs, Takes, #=, VM),
% to have statistics on the resolution of the problem.
time(labeling([max(VM), down], Takes)),
scalar_product(Ws, Takes, #=, WM),
%% displayinf of the results.
compute_lenword(L, 0, Len),
sformat(A1, '~~w~~t~~~w|', [Len]),
sformat(A2, '~~t~~w~~~w|', [4]),
sformat(A3, '~~t~~w~~~w|', [5]),
print_results(A1,A2,A3, L, Takes, WM, VM).
collect((_, W, V, N), W, V, Take) :-
Take in 0..N.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
compute_lenword([], N, N).
compute_lenword([(Name, _, _, _)|T], N, NF):-
atom_length(Name, L),
( L > N -> N1 = L; N1 = N),
compute_lenword(T, N1, NF).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
print_results(A1,A2,A3, [], [], WM, WR) :-
sformat(W0, '~w ', [' ']),
sformat(W1, A1, [' ']),
sformat(W2, A2, [WM]),
sformat(W3, A3, [WR]),
format('~w~w~w~w~n', [W0,W1,W2,W3]).
print_results(A1,A2,A3, [_H|T], [0|TR], WM, VM) :-
!,
print_results(A1,A2,A3, T, TR, WM, VM).
print_results(A1, A2, A3, [(Name, W, V, _)|T], [N|TR], WM, VM) :-
sformat(W0, '~w ', [N]),
sformat(W1, A1, [Name]),
sformat(W2, A2, [W]),
sformat(W3, A3, [V]),
format('~w~w~w~w~n', [W0,W1,W2,W3]),
print_results(A1, A2, A3, T, TR, WM, VM).
- Output:
?- knapsack.
% 21,154,932 inferences, 3.187 CPU in 3.186 seconds (100% CPU, 6638515 Lips)
1 map 9 150
1 compass 13 35
1 water 153 200
2 glucose 15 60
3 banana 27 60
1 cheese 23 30
1 suntan cream 11 70
1 waterproof overclothes 43 75
1 note-case 22 80
1 sunglasses 7 20
1 socks 4 50
396 1010
true
Library simplex
Library simplex is written by Markus Triska. Takes about 10 seconds to compute the best solution.
:- use_module(library(simplex)).
% tuples (name, weights, value, pieces).
knapsack :-
L = [(map, 9, 150, 1),
( compass, 13, 35, 1),
( water, 153, 200, 2),
( sandwich, 50, 60, 2),
( glucose, 15, 60, 2),
( tin, 68, 45, 3),
( banana, 27, 60, 3),
( apple, 39, 40, 3),
( cheese, 23, 30, 1),
( beer, 52, 10, 3),
( 'suntan cream', 11, 70, 1),
( camera, 32, 30, 1),
( 'T-shirt', 24, 15, 2),
( trousers, 48, 10, 2),
( umbrella, 73, 40, 1),
( 'waterproof trousers', 42, 70, 1),
( 'waterproof overclothes', 43, 75, 1),
( 'note-case', 22, 80, 1),
( sunglasses, 7, 20, 1),
( towel, 18, 12, 2),
( socks, 4, 50, 1),
( book, 30, 10, 2)],
gen_state(S0),
length(L, N),
numlist(1, N, LN),
time(( create_constraint_N(LN, L, S0, S1),
maplist(create_constraint_WV, LN, L, LW, LV),
constraint(LW =< 400, S1, S2),
maximize(LV, S2, S3)
)),
compute_lenword(L, 0, Len),
sformat(A1, '~~w~~t~~~w|', [Len]),
sformat(A2, '~~t~~w~~~w|', [4]),
sformat(A3, '~~t~~w~~~w|', [5]),
print_results(S3, A1,A2,A3, L, LN, 0, 0).
create_constraint_N([], [], S, S).
create_constraint_N([HN|TN], [(_, _, _, Nb) | TL], S1, SF) :-
constraint(integral(x(HN)), S1, S2),
constraint([x(HN)] =< Nb, S2, S3),
constraint([x(HN)] >= 0, S3, S4),
create_constraint_N(TN, TL, S4, SF).
create_constraint_WV(N, (_, W, V, _), W * x(N), V * x(N)).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
compute_lenword([], N, N).
compute_lenword([(Name, _, _, _)|T], N, NF):-
atom_length(Name, L),
( L > N -> N1 = L; N1 = N),
compute_lenword(T, N1, NF).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
print_results(_S, A1, A2, A3, [], [], WM, VM) :-
sformat(W0, '~w ', [' ']),
sformat(W1, A1, [' ']),
sformat(W2, A2, [WM]),
sformat(W3, A3, [VM]),
format('~w~w~w~w~n', [W0, W1,W2,W3]).
print_results(S, A1, A2, A3, [(Name, W, V,_)|T], [N|TN], W1, V1) :-
variable_value(S, x(N), X),
( X = 0 -> W1 = W2, V1 = V2
; sformat(S0, '~w ', [X]),
sformat(S1, A1, [Name]),
sformat(S2, A2, [W]),
sformat(S3, A3, [V]),
format('~w~w~w~w~n', [S0, S1,S2,S3]),
W2 is W1 + X * W,
V2 is V1 + X * V),
print_results(S, A1, A2, A3, T, TN, W2, V2).
Python
Not as dumb a search over all possible combinations under the maximum allowed weight:
from itertools import groupby
from collections import namedtuple
def anyvalidcomb(items, maxwt, val=0, wt=0):
' All combinations below the maxwt '
if not items:
yield [], val, wt
else:
this, *items = items # car, cdr
for n in range(this.number + 1):
w = wt + n * this.weight
if w > maxwt:
break
v = val + n * this.value
this_comb = [this] * n
for comb, value, weight in anyvalidcomb(items, maxwt, v, w):
yield this_comb + comb, value, weight
maxwt = 400
COMB, VAL, WT = range(3)
Item = namedtuple('Items', 'name weight value number')
items = [ Item(*x) for x in
(
("map", 9, 150, 1),
("compass", 13, 35, 1),
("water", 153, 200, 3),
("sandwich", 50, 60, 2),
("glucose", 15, 60, 2),
("tin", 68, 45, 3),
("banana", 27, 60, 3),
("apple", 39, 40, 3),
("cheese", 23, 30, 1),
("beer", 52, 10, 3),
("suntan cream", 11, 70, 1),
("camera", 32, 30, 1),
("t-shirt", 24, 15, 2),
("trousers", 48, 10, 2),
("umbrella", 73, 40, 1),
("waterproof trousers", 42, 70, 1),
("waterproof overclothes", 43, 75, 1),
("note-case", 22, 80, 1),
("sunglasses", 7, 20, 1),
("towel", 18, 12, 2),
("socks", 4, 50, 1),
("book", 30, 10, 2),
) ]
bagged = max( anyvalidcomb(items, maxwt), key=lambda c: (c[VAL], -c[WT])) # max val or min wt if values equal
print("Bagged the following %i items" % len(bagged[COMB]))
print('\n\t'.join('%i off: %s' % (len(list(grp)), item.name) for item, grp in groupby(sorted(bagged[COMB]))))
print("for a total value of %i and a total weight of %i" % bagged[1:])
- Output:
Bagged the following 14 items 3 off: banana 1 off: cheese 1 off: compass 2 off: glucose 1 off: map 1 off: note-case 1 off: socks 1 off: sunglasses 1 off: suntan cream 1 off: water 1 off: waterproof overclothes for a total value of 1010 and a total weight of 396
Dynamic programming solution
This is much faster. It expands the multiple possible instances of an item into individual instances then applies the zero-one dynamic knapsack solution:
from itertools import groupby
try:
xrange
except:
xrange = range
maxwt = 400
groupeditems = (
("map", 9, 150, 1),
("compass", 13, 35, 1),
("water", 153, 200, 3),
("sandwich", 50, 60, 2),
("glucose", 15, 60, 2),
("tin", 68, 45, 3),
("banana", 27, 60, 3),
("apple", 39, 40, 3),
("cheese", 23, 30, 1),
("beer", 52, 10, 3),
("suntan cream", 11, 70, 1),
("camera", 32, 30, 1),
("t-shirt", 24, 15, 2),
("trousers", 48, 10, 2),
("umbrella", 73, 40, 1),
("waterproof trousers", 42, 70, 1),
("waterproof overclothes", 43, 75, 1),
("note-case", 22, 80, 1),
("sunglasses", 7, 20, 1),
("towel", 18, 12, 2),
("socks", 4, 50, 1),
("book", 30, 10, 2),
)
items = sum( ([(item, wt, val)]*n for item, wt, val,n in groupeditems), [])
def knapsack01_dp(items, limit):
table = [[0 for w in range(limit + 1)] for j in xrange(len(items) + 1)]
for j in xrange(1, len(items) + 1):
item, wt, val = items[j-1]
for w in xrange(1, limit + 1):
if wt > w:
table[j][w] = table[j-1][w]
else:
table[j][w] = max(table[j-1][w],
table[j-1][w-wt] + val)
result = []
w = limit
for j in range(len(items), 0, -1):
was_added = table[j][w] != table[j-1][w]
if was_added:
item, wt, val = items[j-1]
result.append(items[j-1])
w -= wt
return result
bagged = knapsack01_dp(items, maxwt)
print("Bagged the following %i items\n " % len(bagged) +
'\n '.join('%i off: %s' % (len(list(grp)), item[0])
for item,grp in groupby(sorted(bagged))))
print("for a total value of %i and a total weight of %i" % (
sum(item[2] for item in bagged), sum(item[1] for item in bagged)))
Non-zero-one solution
items = {
"sandwich": (50, 60, 2),
"map": (9, 150, 1),
"compass": (13, 35, 1),
"water": (153, 200, 3),
"glucose": (15, 60, 2),
"tin": (68, 45, 3),
"banana": (27, 60, 3),
"apple": (39, 40, 3),
"cheese": (23, 30, 1),
"beer": (52, 10, 3),
"suntan cream": (11, 70, 1),
"camera": (32, 30, 1),
"t-shirt": (24, 15, 2),
"trousers": (48, 10, 2),
"umbrella": (73, 40, 1),
"w-trousers": (42, 70, 1),
"w-overcoat": (43, 75, 1),
"note-case": (22, 80, 1),
"sunglasses": (7, 20, 1),
"towel": (18, 12, 2),
"socks": (4, 50, 1),
"book": (30, 10, 2),
}
item_keys = list(items.keys())
#cache: could just use memoize module, but explicit caching is clearer
def choose_item(weight, idx, cache):
if idx < 0: return 0, []
k = (weight, idx)
if k in cache: return cache[k]
name, w, v, qty = item_keys[idx], *items[item_keys[idx]]
best_v, best_list = 0, []
for i in range(0, qty + 1):
wlim = weight - i * w
if wlim < 0: break
val, taken = choose_item(wlim, idx - 1, cache)
if val + i * v > best_v:
best_v = val + i * v
best_list = taken[:]
best_list.append((i, name))
cache[k] = [best_v, best_list]
return best_v, best_list
v, lst = choose_item(400, len(items) - 1, {})
w = 0
for cnt, name in lst:
if cnt > 0:
print(cnt, name)
w = w + items[name][0] * cnt
print("Total weight:", w, "Value:", v)
R
Reading in task via web scraping.
library(tidyverse)
library(rvest)
task_html= read_html("http://rosettacode.org/wiki/Knapsack_problem/Bounded")
task_table= html_nodes(html, "table")[[1]] %>%
html_table(table, header= T, trim= T) %>%
set_names(c("items", "weight", "value", "pieces")) %>%
filter(items != "knapsack") %>%
mutate(weight= as.numeric(weight),
value= as.numeric(value),
pieces= as.numeric(pieces))
Solution of the task using genetic algorithm.
library(rgenoud)
fitness= function(x= rep(1, nrow(task_table))){
total_value= sum(task_table$value * x)
total_weight= sum(task_table$weight * x)
ifelse(total_weight <= 400, total_value, 400-total_weight)
}
allowed= matrix(c(rep(0, nrow(task_table)), task_table$pieces), ncol = 2)
set.seed(42)
evolution= genoud(fn= fitness,
nvars= nrow(allowed),
max= TRUE,
pop.size= 10000,
data.type.int= TRUE,
Domains= allowed)
cat("Value: ", evolution$value, "\n")
cat("Weight:", sum(task_table$weight * evolution$par), "dag", "\n")
data.frame(item= task_table$items, pieces= as.integer(solution)) %>%
filter(solution> 0)
- Output:
Value: 1010
Weight: 396 dag
item pieces
1 map 1
2 compass 1
3 sandwich 1
4 glucose 2
5 banana 3
6 apple 2
7 cheese 1
8 suntan cream 1
9 waterproof overclothes 1
10 note-case 1
11 sunglasses 1
12 towel 1
13 socks 1
Racket
The algorithm is nearly a direct translation of Haskell's array-based implementation. However, the data is taken from the webpage itself.
#lang racket
(require net/url html xml xml/path)
(struct item (name mass value count) #:transparent)
;this section is to convert the web page on the problem into the data for the problem
;i don't got time to manually type tables, nevermind that this took longer
(define (group-n n l)
(let group-n ([l l] [acc '()])
(if (null? l)
(reverse acc)
(let-values ([(takes drops) (split-at l n)])
(group-n drops (cons takes acc))))))
(define (atom? x) (not (or (pair? x) (null? x))))
;modified from little schemer...finds nested list where regular member would've returned non-#f
(define (member* x t)
(cond [(null? t) #f]
[(atom? (car t)) (or (and (equal? (car t) x) t)
(member* x (cdr t)))]
[else (or (member* x (car t))
(member* x (cdr t)))]))
(define (addr->xexpr f) (compose xml->xexpr f read-html-as-xml get-pure-port string->url))
(define (read-page) ((addr->xexpr cadr) "http://rosettacode.org/wiki/Knapsack_problem/Bounded"))
(define (get-xml-table xe) (member* 'table xe))
(define (xml-table->item-list xe-table)
;all html table datas
(let* ([strs (se-path*/list '(td) xe-table)]
;4 columns per row
[rows (group-n 4 strs)]
;the last two rows belong to the knapsack entry which we don't want
[rows (take rows (- (length rows) 2))])
(for/list ([r rows])
(let ([r (map string-trim r)])
;convert the weight, value, and pieces columns to numbers and structify it
(apply item (car r) (map string->number (cdr r)))))))
;top-level function to take a string representing a URL and gives the table I didn't want to type
(define addr->item-list (compose xml-table->item-list get-xml-table read-page))
;stores best solution
(struct solution (value choices) #:transparent)
;finds best solution in a list of solutions
(define (best sol-list)
(let best ([l (cdr sol-list)] [bst (car sol-list)])
(match l
['() bst]
[(cons s l) (if (> (solution-value s) (solution-value bst))
(best l s)
(best l bst))])))
;stores the choices leading to best solution...item name and # of that item taken
(struct choice (name count) #:transparent)
;algorithm is derived from Haskell's array-based example
;returns vector of solutions for every natural number capacity up to the input max
(define (solution-vector capacity)
;find best value and items that gave it, trying all items
;first we set up a vector for the best solution found for every capacity
;the best solution found at the beginning has 0 value with no items
(for/fold ([solutions (make-vector (add1 capacity) (solution 0 '()))])
([i (addr->item-list)])
;the new solutions aren't accumulated until after processing all the way through a particular
;capacity, lest capacity c allow capacity c+1 to reuse an item that had been exhausted, i.e.
;we have to move on to the next item before we save ANY solutions found for that item, so they
;must be saved "in parallel" by overwriting the entire vector at once
(for/vector ([target-cap (range 0 (add1 capacity))])
(match-let ([(item name mass value count) i])
;find best solution for item out of every number that can be taken of that item
;we'll call an "item and count of item" a choice
(best (for/list ([n (range 0 (add1 count))])
;ensure mass of this choice is not greater than target capacity
(let ([mass-choice (* n mass)])
(if (> mass-choice target-cap)
(solution 0 '())
;subtract from target capacity the amount taken up by this choice
;use it to get the best solution for THAT capacity
(let ([remaining-cap-solution (vector-ref solutions (- target-cap mass-choice))])
;the new solution found adds the value of this choice to the above value and
;adds the choice itself to the list of choices
(solution (+ (* n value) (solution-value remaining-cap-solution))
(cons (choice name n) (solution-choices remaining-cap-solution))))))))))))
;top level function to convert solution vector into single best answer
(define (knapsack capacity)
;the best solution is not necessarily the one that uses max capacity,
;e.g. if max is 5 and you have items of mass 4 and 5, and the 4 is worth more
(match-let ([(solution value choices) (best (vector->list (solution-vector capacity)))])
(solution value (filter (compose positive? choice-count) choices))))
- Output:
(solution 1010 (list (choice "socks" 1) (choice "sunglasses" 1) (choice "note-case" 1) (choice "waterproof overclothes" 1) (choice "suntan cream" 1) (choice "cheese" 1) (choice "banana" 3) (choice "glucose" 2) (choice "water" 1) (choice "compass" 1) (choice "map" 1)))
Raku
(formerly Perl 6)
Original
Recursive algorithm, with cache. Idiomatic code style, using multi-subs and a class.
my class KnapsackItem { has $.name; has $.weight; has $.unit; }
multi sub pokem ([], $, $v = 0) { $v }
multi sub pokem ([$, *@], 0, $v = 0) { $v }
multi sub pokem ([$i, *@rest], $w, $v = 0) {
my $key = "{+@rest} $w $v";
(state %cache){$key} or do {
my @skip = pokem @rest, $w, $v;
if $w >= $i.weight { # next one fits
my @put = pokem @rest, $w - $i.weight, $v + $i.unit;
return (%cache{$key} = |@put, $i.name).list if @put[0] > @skip[0];
}
return (%cache{$key} = |@skip).list;
}
}
my $MAX_WEIGHT = 400;
my @table = flat map -> $name, $weight, $unit, $count {
KnapsackItem.new( :$name, :$weight, :$unit ) xx $count;
},
'map', 9, 150, 1,
'compass', 13, 35, 1,
'water', 153, 200, 2,
'sandwich', 50, 60, 2,
'glucose', 15, 60, 2,
'tin', 68, 45, 3,
'banana', 27, 60, 3,
'apple', 39, 40, 3,
'cheese', 23, 30, 1,
'beer', 52, 10, 3,
'suntan cream', 11, 70, 1,
'camera', 32, 30, 1,
'T-shirt', 24, 15, 2,
'trousers', 48, 10, 2,
'umbrella', 73, 40, 1,
'waterproof trousers', 42, 70, 1,
'waterproof overclothes', 43, 75, 1,
'note-case', 22, 80, 1,
'sunglasses', 7, 20, 1,
'towel', 18, 12, 2,
'socks', 4, 50, 1,
'book', 30, 10, 2
;
my ($value, @result) = pokem @table, $MAX_WEIGHT;
(my %hash){$_}++ for @result;
say "Value = $value";
say "Tourist put in the bag:";
say " # ITEM";
for %hash.sort -> $item {
say " {$item.value} {$item.key}";
}
- Output:
Value = 1010 Tourist put in the bag: # ITEM 3 banana 1 cheese 1 compass 2 glucose 1 map 1 note-case 1 socks 1 sunglasses 1 suntan cream 1 water 1 waterproof overclothes
Faster alternative
Also recursive, with cache, but substantially faster. Code more generic (ported from Perl solution).
my $raw = qq:to/TABLE/;
map 9 150 1
compass 13 35 1
water 153 200 2
sandwich 50 60 2
glucose 15 60 2
tin 68 45 3
banana 27 60 3
apple 39 40 3
cheese 23 30 1
beer 52 10 1
suntancream 11 70 1
camera 32 30 1
T-shirt 24 15 2
trousers 48 10 2
umbrella 73 40 1
w_trousers 42 70 1
w_overcoat 43 75 1
note-case 22 80 1
sunglasses 7 20 1
towel 18 12 2
socks 4 50 1
book 30 10 2
TABLE
my @items;
for split(["\n", /\s+/], $raw, :skip-empty) -> $n,$w,$v,$q {
@items.push: %{ name => $n, weight => $w, value => $v, quant => $q}
}
my $max_weight = 400;
sub pick ($weight, $pos) {
state %cache;
return 0, 0 if $pos < 0 or $weight <= 0;
my $key = $weight ~ $pos;
%cache{$key} or do {
my %item = @items[$pos];
my ($bv, $bi, $bw, @bp) = (0, 0, 0);
for 0 .. %item{'quant'} -> $i {
last if $i * %item{'weight'} > $weight;
my ($v, $w, @p) = pick($weight - $i * %item{'weight'}, $pos - 1);
next if ($v += $i * %item{'value'}) <= $bv;
($bv, $bi, $bw, @bp) = ($v, $i, $w, |@p);
}
%cache{$key} = $bv, $bw + $bi * %item{'weight'}, |@bp, $bi;
}
}
my ($v, $w, @p) = pick($max_weight, @items.end);
{ say "{@p[$_]} of @items[$_]{'name'}" if @p[$_] } for 0 .. @p.end;
say "Value: $v Weight: $w";
- Output:
1 of map 1 of compass 1 of water 2 of glucose 3 of banana 1 of cheese 1 of suntancream 1 of w_overcoat 1 of note-case 1 of sunglasses 1 of socks Value: 1010 Weight: 396
REXX
Originally, the combination generator/checker subroutine findBest was recursive and made the program solution generic.
However, a recursive solution also made the solution much more slower, so the combination generator/checker was
"unrolled" and converted into discrete combination checks (based on the number of items). The unused combinatorial
checks were discarded and only the pertinent code was retained.
/*REXX program solves a knapsack problem (22 items + repeats, with weight restriction.*/
call @gen /*generate items and initializations. */
call @sort /*sort items by decreasing their weight*/
call build /*build a list of choices (objects). */
call showOBJ /*display the list of choices (objects)*/
call findBest /*examine and find the possible choices*/
call showBest /*display best choice (weight, value).*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
@gen: @.=; @.1 = 'map 9 150'
@.2 = 'compass 13 35'
@.3 = 'water 153 200 2'
@.4 = 'sandwich 50 60 2'
@.5 = 'glucose 15 60 2'
@.6 = 'tin 68 45 3'
@.7 = 'banana 27 60 3'
@.8 = 'apple 39 40 3'
@.9 = 'cheese 23 30'
@.10 = 'beer 52 10 3'
@.11 = 'suntan_cream 11 70'
@.12 = 'camera 32 30'
@.13 = 'T-shirt 24 15 2'
@.14 = 'trousers 48 10 2'
@.15 = 'umbrella 73 40'
@.16 = 'waterproof_trousers 42 70'
@.17 = 'waterproof_overclothes 43 75'
@.18 = 'note-case 22 80'
@.19 = 'sunglasses 7 20'
@.20 = 'towel 18 12 2'
@.21 = 'socks 4 50'
@.22 = 'book 30 10 2'
highQ = 0 /*maximum quantity specified (if any). */
maxL = length('knapsack items') /* " " width for the table names*/
maxW = length('weight') /* " " " " " weights. */
maxV = length('value') /* " " " " " values. */
maxQ = length('pieces') /* " " " " " quantity.*/
maxWeight=400 /*the maximum weight for the knapsack. */
items= 0; i.=; w.=0; v.=0; q.=0 /*initialize some stuff and things. */
Tw= 0; Tv=0; Tq=0; m=maxWeight /* " more " " " */
say; say 'maximum weight allowed for a knapsack: ' commas(maxWeight); say
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
@sort: do j=1 while @.j\=='' /*process each choice and sort the item*/
@.j=space(@.j); _wt=word(@.j, 2) /*choose first item (arbitrary). */
do k=j+1 while @.k\=='' /*find a possible heavier item. */
?wt=word(@.k, 2)
if ?wt>_wt then do; _=@.k; @.k=@.j; @.j=_; _wt=?wt; end /*swap*/
end /*k*/
end /*j*/ /* [↑] minimizes the # of combinations*/
obj=j-1 /*adjust for the DO loop index. */
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
build: do j=1 for obj /*build a list of choices (objects). */
parse var @.j item w v q . /*parse the original choice for table. */
if w>maxWeight then iterate /*Is the weight > maximum? Then ignore*/
Tw=Tw+w; Tv=Tv+v; Tq=Tq+1 /*add the totals up (for alignment). */
maxL=max(maxL, length(item)) /*find the maximum width for an item. */
if q=='' then q=1
highQ=max(highQ, q)
items=items+1 /*bump the item counter. */
i.items=item; w.items=w; v.items=v; q.items=q
do k=2 to q ; items=items+1 /*bump the item counter (each piece). */
i.items=item; w.items=w; v.items=v; q.items=q
Tw=Tw+w; Tv=Tv+v; Tq=Tq+1
end /*k*/
end /*j*/
maxW = max(maxW, length( commas(Tw) ) ) /*find the maximum width for weight. */
maxV = max(maxV, length( commas(Tv) ) ) /* " " " " " value. */
maxQ = max(maxQ, length( commas(Tq) ) ) /* " " " " " quantity. */
maxL = maxL + maxL %4 + 4 /*extend the width of name for table. */
return /* [↑] % is REXX integer division. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: procedure; parse arg _; n=_'.9'; #=123456789; b=verify(n, #, "M"); x=','
e=verify(n, #'0', , verify(n, #"0.", 'M') ) - 4 /* [↓] add commas to number*/
do j=e to b by -3; _=insert(x, _, j); end /*j*/; return _
/*──────────────────────────────────────────────────────────────────────────────────────*/
hdr: parse arg _item_, _; if highq\==1 then _=center('pieces', maxq)
call show center(_item_, maxL), center('weight', maxW), center('value', maxV), ,
center(_ , maxQ); call hdr2; return
/*──────────────────────────────────────────────────────────────────────────────────────*/
hdr2: _=maxQ; x='═'; if highq==1 then _=0
call show copies(x, maxL), copies(x, maxW), copies(x, maxV), copies(x, _); return
/*──────────────────────────────────────────────────────────────────────────────────────*/
j?: parse arg _,?; $=value('Z'_); do k=1 for _; ?=? value('J'k); end; return
/*──────────────────────────────────────────────────────────────────────────────────────*/
show: parse arg _item, _weight, _value, _quant
say translate(left(_item, maxL,'─'), ,'_') right(commas(_weight), maxW),
right(commas(_value ), maxV) right(commas(_quant ), maxQ); return
/*──────────────────────────────────────────────────────────────────────────────────────*/
showOBJ: call hdr 'item'; do j=1 for obj /*show the formatted choices. */
parse var @.j item weight value q .
if highq==1 then q=
else if q=='' then q=1
call show item, weight, value, q
end /*j*/
say; say 'number of unique named items: ' obj
say 'number of items (including reps): ' items; say; return
/*──────────────────────────────────────────────────────────────────────────────────────*/
showBest: do words(?); ?=strip(space(?), "L", 0); end /*words(?)*/
bestC=?; bestW=0; bestV=$; highQ=0; totP=words(bestC); say
call hdr 'best choice'
do j=1 to totP /*J is modified within DO loop.*/
_=word(bestC, j); _w=w._; _v=v._; q=1
if _==0 then iterate
do k=j+1 to totP; __=word(bestC, k) /*get a choice.*/
if i._\==i.__ then leave /*not equal ? */
j=j+1; w._=w._+_w; v._=v._+_v; q=q+1
end /*k*/
call show i._, w._, v._, q; bestW=bestw+w._
end /*j*/
call hdr2; say
call show 'best weight' , bestW /*show a nicely formatted winnerW.*/
call show 'best value' , , bestV /* " " " " winnerV.*/
call show 'knapsack items', , , totP /* " " " " pieces. */
return
/*─────────────────────────────────────────────────────────────────────────────────────────────────────────*/
findBest: h=items; $=0
do j1 =0 for h+1; w1= w.j1 ; z1= v.j1 ;if z1>$ then call j? 1
do j2 =j1 +(j1 >0) to h;if w.j2 +w1 >m then iterate j1; w2=w1 +w.j2 ; z2=z1 +v.j2 ;if z2>$ then call j? 2
do j3 =j2 +(j2 >0) to h;if w.j3 +w2 >m then iterate j2; w3=w2 +w.j3 ; z3=z2 +v.j3 ;if z3>$ then call j? 3
do j4 =j3 +(j3 >0) to h;if w.j4 +w3 >m then iterate j3; w4=w3 +w.j4 ; z4=z3 +v.j4 ;if z4>$ then call j? 4
do j5 =j4 +(j4 >0) to h;if w.j5 +w4 >m then iterate j4; w5=w4 +w.j5 ; z5=z4 +v.j5 ;if z5>$ then call j? 5
do j6 =j5 +(j5 >0) to h;if w.j6 +w5 >m then iterate j5; w6=w5 +w.j6 ; z6=z5 +v.j6 ;if z6>$ then call j? 6
do j7 =j6 +(j6 >0) to h;if w.j7 +w6 >m then iterate j6; w7=w6 +w.j7 ; z7=z6 +v.j7 ;if z7>$ then call j? 7
do j8 =j7 +(j7 >0) to h;if w.j8 +w7 >m then iterate j7; w8=w7 +w.j8 ; z8=z7 +v.j8 ;if z8>$ then call j? 8
do j9 =j8 +(j8 >0) to h;if w.j9 +w8 >m then iterate j8; w9=w8 +w.j9 ; z9=z8 +v.j9 ;if z9>$ then call j? 9
do j10=j9 +(j9 >0) to h;if w.j10+w9 >m then iterate j9;w10=w9 +w.j10;z10=z9 +v.j10;if z10>$ then call j? 10
do j11=j10+(j10>0) to h;if w.j11+w10>m then iterate j10;w11=w10+w.j11;z11=z10+v.j11;if z11>$ then call j? 11
do j12=j11+(j11>0) to h;if w.j12+w11>m then iterate j11;w12=w11+w.j12;z12=z11+v.j12;if z12>$ then call j? 12
do j13=j12+(j12>0) to h;if w.j13+w12>m then iterate j12;w13=w12+w.j13;z13=z12+v.j13;if z13>$ then call j? 13
do j14=j13+(j13>0) to h;if w.j14+w13>m then iterate j13;w14=w13+w.j14;z14=z13+v.j14;if z14>$ then call j? 14
do j15=j14+(j14>0) to h;if w.j15+w14>m then iterate j14;w15=w14+w.j15;z15=z14+v.j15;if z15>$ then call j? 15
do j16=j15+(j15>0) to h;if w.j16+w15>m then iterate j15;w16=w15+w.j16;z16=z15+v.j16;if z16>$ then call j? 16
do j17=j16+(j16>0) to h;if w.j17+w16>m then iterate j16;w17=w16+w.j17;z17=z16+v.j17;if z17>$ then call j? 17
do j18=j17+(j17>0) to h;if w.j18+w17>m then iterate j17;w18=w17+w.j18;z18=z17+v.j18;if z18>$ then call j? 18
do j19=j18+(j18>0) to h;if w.j19+w18>m then iterate j18;w19=w18+w.j19;z19=z18+v.j19;if z19>$ then call j? 19
do j20=j19+(j19>0) to h;if w.j20+w19>m then iterate j19;w20=w19+w.j20;z20=z19+v.j20;if z20>$ then call j? 20
do j21=j20+(j20>0) to h;if w.j21+w20>m then iterate j20;w21=w20+w.j21;z21=z20+v.j21;if z21>$ then call j? 21
do j22=j21+(j21>0) to h;if w.j22+w21>m then iterate j21;w22=w21+w.j22;z22=z21+v.j22;if z22>$ then call j? 22
do j23=j22+(j22>0) to h;if w.j23+w22>m then iterate j22;w23=w22+w.j23;z23=z22+v.j23;if z23>$ then call j? 23
do j24=j23+(j23>0) to h;if w.j24+w23>m then iterate j23;w24=w23+w.j24;z24=z23+v.j24;if z24>$ then call j? 24
do j25=j24+(j24>0) to h;if w.j25+w24>m then iterate j24;w25=w24+w.j25;z25=z24+v.j25;if z25>$ then call j? 25
do j26=j25+(j25>0) to h;if w.j26+w25>m then iterate j25;w26=w25+w.j26;z26=z25+v.j26;if z26>$ then call j? 26
do j27=j26+(j26>0) to h;if w.j27+w26>m then iterate j26;w27=w26+w.j27;z27=z26+v.j27;if z27>$ then call j? 27
do j28=j27+(j27>0) to h;if w.j28+w27>m then iterate j27;w28=w27+w.j28;z28=z27+v.j28;if z28>$ then call j? 28
do j29=j28+(j28>0) to h;if w.j29+w28>m then iterate j28;w29=w28+w.j29;z29=z28+v.j29;if z29>$ then call j? 29
do j30=j29+(j29>0) to h;if w.j30+w29>m then iterate j29;w30=w29+w.j30;z30=z29+v.j30;if z30>$ then call j? 30
do j31=j30+(j30>0) to h;if w.j31+w30>m then iterate j30;w31=w30+w.j31;z31=z30+v.j31;if z31>$ then call j? 31
do j32=j31+(j31>0) to h;if w.j32+w31>m then iterate j31;w32=w31+w.j32;z32=z31+v.j32;if z32>$ then call j? 32
do j33=j32+(j32>0) to h;if w.j33+w32>m then iterate j32;w33=w32+w.j33;z33=z32+v.j33;if z33>$ then call j? 33
do j34=j33+(j33>0) to h;if w.j34+w33>m then iterate j33;w34=w33+w.j34;z34=z33+v.j34;if z34>$ then call j? 34
do j35=j34+(j34>0) to h;if w.j35+w34>m then iterate j34;w35=w34+w.j35;z35=z34+v.j35;if z35>$ then call j? 35
do j36=j35+(j35>0) to h;if w.j36+w35>m then iterate j35;w36=w35+w.j36;z36=z35+v.j36;if z36>$ then call j? 36
do j37=j36+(j36>0) to h;if w.j37+w36>m then iterate j36;w37=w36+w.j37;z37=z36+v.j37;if z37>$ then call j? 37
end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end
end;end;end;end;end;end;end;end;end;end; return /* [↑] there is one END for each DO loop.*/
output
maximum weight allowed for a knapsack: 400
item weight value pieces
═══════════════════════════════ ══════ ═════ ══════
water────────────────────────── 153 200 2
umbrella─────────────────────── 73 40 1
tin──────────────────────────── 68 45 3
beer─────────────────────────── 52 10 3
sandwich─────────────────────── 50 60 2
trousers─────────────────────── 48 10 2
waterproof overclothes───────── 43 75 1
waterproof trousers──────────── 42 70 1
apple────────────────────────── 39 40 3
camera───────────────────────── 32 30 1
book─────────────────────────── 30 10 2
banana───────────────────────── 27 60 3
T-shirt──────────────────────── 24 15 2
cheese───────────────────────── 23 30 1
note-case────────────────────── 22 80 1
towel────────────────────────── 18 12 2
glucose──────────────────────── 15 60 2
compass──────────────────────── 13 35 1
suntan cream─────────────────── 11 70 1
map──────────────────────────── 9 150 1
sunglasses───────────────────── 7 20 1
socks────────────────────────── 4 50 1
number of items (with repetitions): 37
best choice weight value pieces
═══════════════════════════════ ══════ ═════ ══════
water────────────────────────── 153 200 1
waterproof overclothes───────── 43 75 1
banana───────────────────────── 81 180 3
cheese───────────────────────── 23 30 1
note-case────────────────────── 22 80 1
glucose──────────────────────── 30 120 2
compass──────────────────────── 13 35 1
suntan cream─────────────────── 11 70 1
map──────────────────────────── 9 150 1
sunglasses───────────────────── 7 20 1
socks────────────────────────── 4 50 1
═══════════════════════════════ ══════ ═════ ══════
best weight──────────────────── 396
best value───────────────────── 1,010
knapsack items───────────────── 14
Ruby
# Item struct to represent each item in the problem
Struct.new('Item', :name, :weight, :value, :count)
$items = [
Struct::Item.new('map', 9, 150, 1),
Struct::Item.new('compass', 13, 35, 1),
Struct::Item.new('water', 153, 200, 3),
Struct::Item.new('sandwich', 50, 60, 2),
Struct::Item.new('glucose', 15, 60, 2),
Struct::Item.new('tin', 68, 45, 3),
Struct::Item.new('banana', 27, 60, 3),
Struct::Item.new('apple', 39, 40, 3),
Struct::Item.new('cheese', 23, 30, 1),
Struct::Item.new('beer', 52, 10, 3),
Struct::Item.new('suntan cream', 11, 70, 1),
Struct::Item.new('camera', 32, 30, 1),
Struct::Item.new('t-shirt', 24, 15, 2),
Struct::Item.new('trousers', 48, 10, 2),
Struct::Item.new('umbrella', 73, 40, 1),
Struct::Item.new('w-trousers', 42, 70, 1),
Struct::Item.new('w-overcoat', 43, 75, 1),
Struct::Item.new('note-case', 22, 80, 1),
Struct::Item.new('sunglasses', 7, 20, 1),
Struct::Item.new('towel', 18, 12, 2),
Struct::Item.new('socks', 4, 50, 1),
Struct::Item.new('book', 30, 10, 2)
]
def choose_item(weight, id, cache)
return 0, [] if id < 0
k = [weight, id]
return cache[k] unless cache[k].nil?
value = $items[id].value
best_v = 0
best_list = []
($items[id].count+1).times do |i|
wlim = weight - i * $items[id].weight
break if wlim < 0
val, taken = choose_item(wlim, id - 1, cache)
if val + i * value > best_v
best_v = val + i * value
best_list = taken + [i]
end
end
cache[k] = [best_v, best_list]
return [best_v, best_list]
end
val, list = choose_item(400, $items.length - 1, {})
w = 0
list.each_with_index do |cnt, i|
if cnt > 0
print "#{cnt} #{$items[i].name}\n"
w += $items[i][1] * cnt
end
end
p "Total weight: #{w}, Value: #{val}"
SAS
Use MILP solver in SAS/OR:
/* create SAS data set */
data mydata;
input item $1-23 weight value pieces;
datalines;
map 9 150 1
compass 13 35 1
water 153 200 2
sandwich 50 60 2
glucose 15 60 2
tin 68 45 3
banana 27 60 3
apple 39 40 3
cheese 23 30 1
beer 52 10 3
suntan cream 11 70 1
camera 32 30 1
T-shirt 24 15 2
trousers 48 10 2
umbrella 73 40 1
waterproof trousers 42 70 1
waterproof overclothes 43 75 1
note-case 22 80 1
sunglasses 7 20 1
towel 18 12 2
socks 4 50 1
book 30 10 2
;
/* call OPTMODEL procedure in SAS/OR */
proc optmodel;
/* declare sets and parameters, and read input data */
set <str> ITEMS;
num weight {ITEMS};
num value {ITEMS};
num pieces {ITEMS};
read data mydata into ITEMS=[item] weight value pieces;
/* declare variables, objective, and constraints */
var NumSelected {i in ITEMS} >= 0 <= pieces[i] integer;
max TotalValue = sum {i in ITEMS} value[i] * NumSelected[i];
con WeightCon:
sum {i in ITEMS} weight[i] * NumSelected[i] <= 400;
/* call mixed integer linear programming (MILP) solver */
solve;
/* print optimal solution */
print TotalValue;
print {i in ITEMS: NumSelected[i].sol > 0.5} NumSelected;
quit;
Output:
TotalValue 1010 [1] NumSelected banana 3 cheese 1 compass 1 glucose 2 map 1 note-case 1 socks 1 sunglasses 1 suntan cream 1 water 1 waterproof overclothes 1
Sidef
var raw = <<'TABLE'
map 9 150 1
compass 13 35 1
water 153 200 2
sandwich 50 60 2
glucose 15 60 2
tin 68 45 3
banana 27 60 3
apple 39 40 3
cheese 23 30 1
beer 52 10 1
suntancream 11 70 1
camera 32 30 1
T-shirt 24 15 2
trousers 48 10 2
umbrella 73 40 1
w_trousers 42 70 1
w_overcoat 43 75 1
note-case 22 80 1
sunglasses 7 20 1
towel 18 12 2
socks 4 50 1
book 30 10 2
TABLE
struct KnapsackItem {
String name,
Number weight,
Number value,
Number quant,
}
var items = []
raw.each_line{ |row|
var fields = row.words;
items << KnapsackItem(
name: fields[0],
weight: fields[1].to_n,
value: fields[2].to_n,
quant: fields[3].to_n,
)
}
func pick(weight, pos) is cached {
if (pos.is_neg || weight.is_neg || weight.is_zero) {
return (0, 0, [])
}
var (bv=0, bi=0, bw=0, bp=[])
var item = items[pos];
for i in range(0, item.quant) {
break if (i*item.weight > weight)
var (v, w, p) = pick(weight - i*item.weight, pos.dec)
next if ((v += i*item.value) <= bv)
(bv, bi, bw, bp) = (v, i, w, p)
}
(bv, bw + bi*item.weight, [bp..., bi])
}
var (v, w, p) = pick(400, items.end)
p.range.each { |i|
say "#{p[i]} of #{items[i].name}" if p[i].is_pos
}
say "Value: #{v}; Weight: #{w}"
- Output:
1 of map 1 of compass 1 of water 2 of glucose 3 of banana 1 of cheese 1 of suntancream 1 of w_overcoat 1 of note-case 1 of sunglasses 1 of socks Value: 1010; Weight: 396
Swift
public struct KnapsackItem: Hashable {
public var name: String
public var weight: Int
public var value: Int
public init(name: String, weight: Int, value: Int) {
self.name = name
self.weight = weight
self.value = value
}
}
public func knapsack(items: [KnapsackItem], limit: Int) -> [KnapsackItem] {
var table = Array(repeating: Array(repeating: 0, count: limit + 1), count: items.count + 1)
for j in 1...items.count {
let item = items[j-1]
for w in 1...limit {
if item.weight > w {
table[j][w] = table[j-1][w]
} else {
table[j][w] = max(table[j-1][w], table[j-1][w-item.weight] + item.value)
}
}
}
var result = [KnapsackItem]()
var w = limit
for j in stride(from: items.count, to: 0, by: -1) where table[j][w] != table[j-1][w] {
let item = items[j-1]
result.append(item)
w -= item.weight
}
return result
}
typealias GroupedItem = (name: String, weight: Int, val: Int, n: Int)
let groupedItems: [GroupedItem] = [
("map", 9, 150, 1),
("compass", 13, 35, 1),
("water", 153, 200, 3),
("sandwich", 50, 60, 2),
("glucose", 15, 60, 2),
("tin", 68, 45, 3),
("banana", 27, 60, 3),
("apple", 39, 40, 3),
("cheese", 23, 30, 1),
("beer", 52, 10, 3),
("suntan cream", 11, 70, 1),
("camera", 32, 30, 1),
("t-shirt", 24, 15, 2),
("trousers", 48, 10, 2),
("umbrella", 73, 40, 1),
("waterproof trousers", 42, 70, 1),
("waterproof overclothes", 43, 75, 1),
("note-case", 22, 80, 1),
("sunglasses", 7, 20, 1),
("towel", 18, 12, 2),
("socks", 4, 50, 1),
("book", 30, 10, 2)
]
let items = groupedItems.flatMap({item in
(0..<item.n).map({_ in KnapsackItem(name: item.name, weight: item.weight, value: item.val) })
})
let bagged = knapsack(items: items, limit: 400)
let (totalVal, totalWeight) = bagged.reduce((0, 0), {cur, item in (cur.0 + item.value, cur.1 + item.weight) })
print("Bagged the following \(bagged.count) items:")
for item in bagged {
print("\t\(item.name)")
}
print("For a total value of \(totalVal) and weight of \(totalWeight)")
- Output:
Bagged the following 14 items: socks sunglasses note-case waterproof overclothes suntan cream cheese banana banana banana glucose glucose water compass map For a total value of 1010 and weight of 396
Tcl
Classic dumb search algorithm:
# The list of items to consider, as list of lists
set items {
{map 9 150 1}
{compass 13 35 1}
{water 153 200 2}
{sandwich 50 60 2}
{glucose 15 60 2}
{tin 68 45 3}
{banana 27 60 3}
{apple 39 40 3}
{cheese 23 30 1}
{beer 52 10 3}
{{suntan cream} 11 70 1}
{camera 32 30 1}
{t-shirt 24 15 2}
{trousers 48 10 2}
{umbrella 73 40 1}
{{waterproof trousers} 42 70 1}
{{waterproof overclothes} 43 75 1}
{note-case 22 80 1}
{sunglasses 7 20 1}
{towel 18 12 2}
{socks 4 50 1}
{book 30 10 2}
}
# Simple extraction functions
proc countednames {chosen} {
set names {}
foreach item $chosen {
lappend names [lindex $item 3] [lindex $item 0]
}
return $names
}
proc weight {chosen} {
set weight 0
foreach item $chosen {
incr weight [expr {[lindex $item 3] * [lindex $item 1]}]
}
return $weight
}
proc value {chosen} {
set value 0
foreach item $chosen {
incr value [expr {[lindex $item 3] * [lindex $item 2]}]
}
return $value
}
# Recursive function for searching over all possible choices of items
proc knapsackSearch {items {chosen {}}} {
# If we've gone over the weight limit, stop now
if {[weight $chosen] > 400} {
return
}
# If we've considered all of the items (i.e., leaf in search tree)
# then see if we've got a new best choice.
if {[llength $items] == 0} {
global best max
set v [value $chosen]
if {$v > $max} {
set max $v
set best $chosen
}
return
}
# Branch, so recurse for chosing the current item or not
set this [lindex $items 0]
set rest [lrange $items 1 end]
knapsackSearch $rest $chosen
for {set i 1} {$i<=[lindex $this 3]} {incr i} {
knapsackSearch $rest \
[concat $chosen [list [lreplace $this end end $i]]]
}
}
# Initialize a few global variables
set best {}
set max 0
# Do the brute-force search
knapsackSearch $items
# Pretty-print the results
puts "Best filling has weight of [expr {[weight $best]/100.0}]kg and score [value $best]"
puts "Best items:"
foreach {count item} [countednames $best] {
puts "\t$count * $item"
}
- Output:
Best filling has weight of 3.96kg and score 1010 Best items: 1 * map 1 * compass 1 * water 2 * glucose 3 * banana 1 * cheese 1 * suntan cream 1 * waterproof overclothes 1 * note-case 1 * sunglasses 1 * socks
Ursala
Instead of an ad-hoc solution, we can convert this task to a mixed integer programming problem instance and solve it with the lpsolve library, which is callable in Ursala.
#import std
#import flo
#import lin
items = # name: (weight,value,limit)
<
'map': (9,150,1),
'compass': (13,35,1),
'water': (153,200,3),
'sandwich': (50,60,2),
'glucose': (15,60,2),
'tin': (68,45,3),
'banana': (27,60,3),
'apple': (39,40,3),
'cheese': (23,30,1),
'beer': (52,10,3),
'suntan cream': (11,70,1),
'camera': (32,30,1),
't-shirt': (24,15,2),
'trousers': (48,10,2),
'umbrella': (73,40,1),
'waterproof trousers': (42,70,1),
'waterproof overclothes': (43,75,1),
'note-case': (22,80,1),
'sunglasses': (7,20,1),
'towel': (18,12,2),
'socks': (4,50,1),
'book': (30,10,2)>
system = # convert the item list to mixed integer programming problem specification
linear_system$[
integers: ~&nS,
upper_bounds: * ^|/~& float@rr,
lower_bounds: @nS ~&\*0.+ :/'(slack)',
costs: * ^|/~& negative+ float@rl,
equations: ~&iNC\400.+ :/(1.,'(slack)')+ * ^|rlX/~& float@l]
format = @t --^*p\pad` @nS @mS printf/*'%0.0f '
#show+
main = format solution system itemsThe linear_system$[...] function takes the item list as an argument and returns a data structure with the following fields, which is passed to the solution function, which calls the lpsolve routines.
integersdeclares that all variables in the list take integer valuesupper_boundsassociates an upper bound for each variable directly as givenlower_boundsare zero for all variables in the table, and for an additional slack variable, which is not required to be an integer and won't appear in the solutioncostsare also taken from the table and negated because their value is to be maximized rather than minimized as in the standard formulationequationsspecifies the single constraint that the total weights of the selected items in the selected quantities plus the slack equal 400
The format function converts the output list to a readable form.
- Output:
3 banana 1 cheese 1 compass 2 glucose 1 map 1 note-case 1 socks 1 sunglasses 1 suntan cream 1 water 1 waterproof overclothes
Wren
import "./fmt" for Fmt
class Item {
construct new(name, weight, value, count) {
_name = name
_weight = weight
_value = value
_count = count
}
name { _name }
weight { _weight }
value { _value }
count { _count }
}
var items = [
Item.new("map", 9, 150, 1),
Item.new("compass", 13, 35, 1),
Item.new("water", 153, 200, 2),
Item.new("sandwich", 50, 60, 2),
Item.new("glucose", 15, 60, 2),
Item.new("tin", 68, 45, 3),
Item.new("banana", 27, 60, 3),
Item.new("apple", 39, 40, 3),
Item.new("cheese", 23, 30, 1),
Item.new("beer", 52, 10, 3),
Item.new("suntan cream", 11, 70, 1),
Item.new("camera", 32, 30, 1),
Item.new("T-shirt", 24, 15, 2),
Item.new("trousers", 48, 10, 2),
Item.new("umbrella", 73, 40, 1),
Item.new("waterproof trousers", 42, 70, 1),
Item.new("waterproof overclothes", 43, 75, 1),
Item.new("note-case", 22, 80, 1),
Item.new("sunglasses", 7, 20, 1),
Item.new("towel", 18, 12, 2),
Item.new("socks", 4, 50, 1),
Item.new("book", 30, 10, 2)
]
var n = items.count
var maxWeight = 400
var knapsack = Fn.new { |w|
var m = List.filled(n + 1, null)
for (i in 0..n) m[i] = List.filled(w + 1, 0)
for (i in 1..n) {
for (j in 0..w) {
m[i][j] = m[i-1][j]
for (k in 1..items[i - 1].count) {
if (k * items[i - 1].weight > j) break
var v = m[i - 1][j - k * items[i - 1].weight] + k * items[i - 1].value
if (v > m[i][j]) m[i][j] = v
}
}
}
var s = List.filled(n, 0)
var j = w
for (i in n..1) {
var v = m[i][j]
var k = 0
while (v != m[i - 1][j] + k * items[i - 1].value) {
s[i - 1] = s[i - 1] + 1
j = j - items[i