Knapsack problem/0-1: Difference between revisions
→{{header|Python}}: added dynamic programming solution |
|||
Line 62: | Line 62: | ||
'''Which items does the tourist carry in his knapsack so that their total weight does not exceed 4 kg, and their total value is maximised?''' |
'''Which items does the tourist carry in his knapsack so that their total weight does not exceed 4 kg, and their total value is maximised?''' |
||
=={{header|D}}== |
|||
D V.2 code, from the Python solution. |
|||
<lang d> |
|||
import std.stdio: writeln; |
|||
import std.algorithm: max; |
|||
import std.typecons: tuple; |
|||
struct Item { |
|||
string name; |
|||
int weight, value; |
|||
} |
|||
Item[] knapsack01_din_prog(const Item[] items, int limit) { |
|||
auto tab = new int[][](items.length + 1, limit + 1); |
|||
foreach (j; 1 .. items.length + 1) { |
|||
int wt = items[j-1].weight; // no handy tuple unpacking |
|||
int val = items[j-1].value; |
|||
foreach (w; 1 .. limit + 1) |
|||
tab[j][w] = (wt > w) ? tab[j-1][w] : max(tab[j-1][w], tab[j-1][w-wt] + val); |
|||
} |
|||
Item[] result; |
|||
int w = limit; |
|||
for (int j = items.length; j > 0; j--) // foreach can't be used here |
|||
if (tab[j][w] != tab[j-1][w]) { |
|||
w -= items[j-1].weight; |
|||
result ~= items[j-1]; |
|||
} |
|||
return result; |
|||
} |
|||
/// Totalise a particular combination of items |
|||
auto solution_value(const Item[] comb, int limit) { |
|||
int tot_w, tot_v; |
|||
foreach (item; comb) { |
|||
tot_w += item.weight; |
|||
tot_v += item.value; |
|||
} |
|||
return (tot_w <= limit) ? tuple(tot_v, -tot_w) : tuple(0, 0); |
|||
} |
|||
void main() { |
|||
enum Item[] items = [ |
|||
{"map", 9, 150}, |
|||
{"compass", 13, 35}, |
|||
{"water", 153, 200}, |
|||
{"sandwich", 50, 160}, |
|||
{"glucose", 15, 60}, |
|||
{"tin", 68, 45}, |
|||
{"banana", 27, 60}, |
|||
{"apple", 39, 40}, |
|||
{"cheese", 23, 30}, |
|||
{"beer", 52, 10}, |
|||
{"suntan cream", 11, 70}, |
|||
{"camera", 32, 30}, |
|||
{"t-shirt", 24, 15}, |
|||
{"trousers", 48, 10}, |
|||
{"umbrella", 73, 40}, |
|||
{"waterproof trousers", 42, 70}, |
|||
{"waterproof overclothes", 43, 75}, |
|||
{"note-case", 22, 80}, |
|||
{"sunglasses", 7, 20}, |
|||
{"towel", 18, 12}, |
|||
{"socks", 4, 50}, |
|||
{"book", 30, 10}]; |
|||
auto bagged = knapsack01_din_prog(items, 400); |
|||
writeln("Bagged the following items:"); |
|||
foreach (item; bagged.sort) |
|||
writeln(" ", item.name); |
|||
auto val_wt = solution_value(bagged, 400); |
|||
writeln("For a total value of ", val_wt.field[0], |
|||
" and a total weight of ", -val_wt.field[1]); |
|||
} |
|||
</lang> |
|||
=={{header|Java}}== |
=={{header|Java}}== |
Revision as of 01:02, 16 February 2010
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
See also: Knapsack problem/Unbounded, Knapsack problem/Bounded
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 to pack well for the trip. He has a good knapsack for carrying things, but knows that he can carry a maximum of only 4kg in it and it will have to last the whole day. He creates a list of what he wants to bring for the trip but the total weight of all items is too much. He then decides to add columns to his initial list detailing their weights and a numerical "value" representing how important the item is for the tour.
Here is the list:
Item | Weight (dag) | Value |
---|---|---|
map | 9 | 150 |
compass | 13 | 35 |
water | 153 | 200 |
sandwich | 50 | 160 |
glucose | 15 | 60 |
tin | 68 | 45 |
banana | 27 | 60 |
apple | 39 | 40 |
cheese | 23 | 30 |
beer | 52 | 10 |
suntan cream | 11 | 70 |
camera | 32 | 30 |
t-shirt | 24 | 15 |
trousers | 48 | 10 |
umbrella | 73 | 40 |
waterproof trousers | 42 | 70 |
waterproof overclothes | 43 | 75 |
note-case | 22 | 80 |
sunglasses | 7 | 20 |
towel | 18 | 12 |
socks | 4 | 50 |
book | 30 | 10 |
Knapsack | <=400 dag | ? |
The tourist can choose to take any combination of items from the list, but only one of each item is available. He do not may cut the items, so he can only take whole units of any item.
Which items does the tourist carry in his knapsack so that their total weight does not exceed 4 kg, and their total value is maximised?
D
D V.2 code, from the Python solution. <lang d> import std.stdio: writeln; import std.algorithm: max; import std.typecons: tuple;
struct Item {
string name; int weight, value;
}
Item[] knapsack01_din_prog(const Item[] items, int limit) {
auto tab = new int[][](items.length + 1, limit + 1);
foreach (j; 1 .. items.length + 1) { int wt = items[j-1].weight; // no handy tuple unpacking int val = items[j-1].value; foreach (w; 1 .. limit + 1) tab[j][w] = (wt > w) ? tab[j-1][w] : max(tab[j-1][w], tab[j-1][w-wt] + val); }
Item[] result; int w = limit; for (int j = items.length; j > 0; j--) // foreach can't be used here if (tab[j][w] != tab[j-1][w]) { w -= items[j-1].weight; result ~= items[j-1]; }
return result;
}
/// Totalise a particular combination of items auto solution_value(const Item[] comb, int limit) {
int tot_w, tot_v; foreach (item; comb) { tot_w += item.weight; tot_v += item.value; } return (tot_w <= limit) ? tuple(tot_v, -tot_w) : tuple(0, 0);
}
void main() {
enum Item[] items = [ {"map", 9, 150}, {"compass", 13, 35}, {"water", 153, 200}, {"sandwich", 50, 160}, {"glucose", 15, 60}, {"tin", 68, 45}, {"banana", 27, 60}, {"apple", 39, 40}, {"cheese", 23, 30}, {"beer", 52, 10}, {"suntan cream", 11, 70}, {"camera", 32, 30}, {"t-shirt", 24, 15}, {"trousers", 48, 10}, {"umbrella", 73, 40}, {"waterproof trousers", 42, 70}, {"waterproof overclothes", 43, 75}, {"note-case", 22, 80}, {"sunglasses", 7, 20}, {"towel", 18, 12}, {"socks", 4, 50}, {"book", 30, 10}];
auto bagged = knapsack01_din_prog(items, 400); writeln("Bagged the following items:"); foreach (item; bagged.sort) writeln(" ", item.name); auto val_wt = solution_value(bagged, 400); writeln("For a total value of ", val_wt.field[0], " and a total weight of ", -val_wt.field[1]);
} </lang>
Java
General dynamic solution after wikipedia.
<lang java> package hu.pj.alg.test;
import hu.pj.alg.ZeroOneKnapsack; import hu.pj.obj.Item; import java.util.*; import java.text.*;
public class ZeroOneKnapsackForTourists {
public ZeroOneKnapsackForTourists() { ZeroOneKnapsack zok = new ZeroOneKnapsack(400); // 400 dkg = 400 dag = 4 kg
// making the list of items that you want to bring zok.add("map", 9, 150); zok.add("compass", 13, 35); zok.add("water", 153, 200); zok.add("sandwich", 50, 160); zok.add("glucose", 15, 60); zok.add("tin", 68, 45); zok.add("banana", 27, 60); zok.add("apple", 39, 40); zok.add("cheese", 23, 30); zok.add("beer", 52, 10); zok.add("suntan cream", 11, 70); zok.add("camera", 32, 30); zok.add("t-shirt", 24, 15); zok.add("trousers", 48, 10); zok.add("umbrella", 73, 40); zok.add("waterproof trousers", 42, 70); zok.add("waterproof overclothes", 43, 75); zok.add("note-case", 22, 80); zok.add("sunglasses", 7, 20); zok.add("towel", 18, 12); zok.add("socks", 4, 50); zok.add("book", 30, 10);
// calculate the solution: List<Item> itemList = zok.calcSolution();
// write out the solution in the standard output if (zok.isCalculated()) { NumberFormat nf = NumberFormat.getInstance();
System.out.println( "Maximal weight = " + nf.format(zok.getMaxWeight() / 100.0) + " kg" ); System.out.println( "Total weight of solution = " + nf.format(zok.getSolutionWeight() / 100.0) + " kg" ); System.out.println( "Total value = " + zok.getProfit() ); System.out.println(); System.out.println( "You can carry te following materials " + "in the knapsack:" ); for (Item item : itemList) { if (item.getInKnapsack() == 1) { System.out.format( "%1$-23s %2$-3s %3$-5s %4$-15s \n", item.getName(), item.getWeight(), "dag ", "(value = " + item.getValue() + ")" ); } } } else { System.out.println( "The problem is not solved. " + "Maybe you gave wrong data." ); }
}
public static void main(String[] args) { new ZeroOneKnapsackForTourists(); }
} // class </lang>
<lang java> 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 </lang>
<lang java> 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 </lang>
output:
Maximal weight = 4 kg Total weight of solution = 3,96 kg Total value = 1030 You can carry te following materials in the knapsack: map 9 dag (value = 150) compass 13 dag (value = 35) water 153 dag (value = 200) sandwich 50 dag (value = 160) glucose 15 dag (value = 60) banana 27 dag (value = 60) suntan cream 11 dag (value = 70) waterproof trousers 42 dag (value = 70) waterproof overclothes 43 dag (value = 75) note-case 22 dag (value = 80) sunglasses 7 dag (value = 20) socks 4 dag (value = 50)
Oz
Using constraint programming. <lang oz>declare
%% maps items to pairs of Weight(hectogram) and Value Problem = knapsack('map':9#150 'compass':13#35 'water':153#200 'sandwich':50#160 'glucose':15#60 'tin':68#45 'banana':27#60 'apple':39#40 'cheese':23#30 'beer':52#10 'suntan cream':11#70 'camera':32#30 't-shirt':24#15 'trousers':48#10 'umbrella':73#40 'waterproof trousers':42#70 'waterproof overclothes':43#75 'note-case':22#80 'sunglasses':7#20 'towel':18#12 'socks':4#50 'book':30#10 )
%% 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 %% with the domain {0,1} Solution = {Record.map Problem fun {$ _} {FD.int 0#1} 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: "} {ForAll {Record.arity {Record.filter Best fun {$ T} T == 1 end}} System.showInfo} {System.printInfo "\n"} {System.showInfo "total value: "#{Value Best}} {System.showInfo "total weight: "#{Weight Best}}</lang>
Output:
Items: banana compass glucose map note-case sandwich socks sunglasses suntan cream water waterproof overclothes waterproof trousers total value: 1030 total weight: 396
Typically runs in less than 150 milliseconds.
Python
Dumb, brute force algorithm: <lang python>from itertools import combinations
def anycomb(items):
' return combinations of any length from the items ' return ( comb for r in range(1, len(items)+1) for comb in combinations(items, r) )
def totalvalue(comb):
' Totalise a particular combination of items' totwt = totval = 0 for item, wt, val in comb: totwt += wt totval += val return (totval, -totwt) if totwt <= 400 else (0, 0)
items = (
("map", 9, 150), ("compass", 13, 35), ("water", 153, 200), ("sandwich", 50, 160), ("glucose", 15, 60), ("tin", 68, 45), ("banana", 27, 60), ("apple", 39, 40), ("cheese", 23, 30), ("beer", 52, 10), ("suntan cream", 11, 70), ("camera", 32, 30), ("t-shirt", 24, 15), ("trousers", 48, 10), ("umbrella", 73, 40), ("waterproof trousers", 42, 70), ("waterproof overclothes", 43, 75), ("note-case", 22, 80), ("sunglasses", 7, 20), ("towel", 18, 12), ("socks", 4, 50), ("book", 30, 10), )
bagged = max( anycomb(items), key=totalvalue) # max val or min wt if values equal print("Bagged the following items\n " +
'\n '.join(sorted(item for item,_,_ in bagged)))
val, wt = totalvalue(bagged) print("for a total value of %i and a total weight of %i" % (val, -wt))</lang> Sample output:
Bagged the following items banana compass glucose map note-case sandwich socks sunglasses suntan cream water waterproof overclothes waterproof trousers for a total value of 1030 and a total weight of 396
Dynamic programming solution
<lang python>def totalvalue(comb):
' Totalise a particular combination of items' totwt = totval = 0 for item, wt, val in comb: totwt += wt totval += val return (totval, -totwt) if totwt <= 400 else (0, 0)
items = (
("map", 9, 150), ("compass", 13, 35), ("water", 153, 200), ("sandwich", 50, 160), ("glucose", 15, 60), ("tin", 68, 45), ("banana", 27, 60), ("apple", 39, 40), ("cheese", 23, 30), ("beer", 52, 10), ("suntan cream", 11, 70), ("camera", 32, 30), ("t-shirt", 24, 15), ("trousers", 48, 10), ("umbrella", 73, 40), ("waterproof trousers", 42, 70), ("waterproof overclothes", 43, 75), ("note-case", 22, 80), ("sunglasses", 7, 20), ("towel", 18, 12), ("socks", 4, 50), ("book", 30, 10), )
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, 400)
print("Bagged the following items\n " +
'\n '.join(sorted(item for item,_,_ in bagged)))
val, wt = totalvalue(bagged) print("for a total value of %i and a total weight of %i" % (val, -wt))</lang>
Tcl
As the saying goes, “when in doubt, try brute force”. Since there's only 22 items we can simply iterate over all possible choices. <lang tcl># The list of items to consider, as list of lists set items {
{map 9 150} {compass 13 35} {water 153 200} {sandwich 50 160} {glucose 15 60} {tin 68 45} {banana 27 60} {apple 39 40} {cheese 23 30} {beer 52 10} {{suntan cream} 11 70} {camera 32 30} {t-shirt 24 15} {trousers 48 10} {umbrella 73 40} {{waterproof trousers} 42 70} {{waterproof overclothes} 43 75} {note-case 22 80} {sunglasses 7 20} {towel 18 12} {socks 4 50} {book 30 10}
}
- Simple extraction functions
proc names {chosen} {
set names {} foreach item $chosen {lappend names [lindex $item 0]} return $names
} proc weight {chosen} {
set weight 0 foreach item $chosen {incr weight [lindex $item 1]} return $weight
} proc value {chosen} {
set value 0 foreach item $chosen {incr value [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 knapsackSearch $rest [lappend chosen $this]
}
- 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:\n\t[join [lsort [names $best]] \n\t]"</lang> Output:
Best filling has weight of 3.96kg and score 1030 Best items: banana compass glucose map note-case sandwich socks sunglasses suntan cream water waterproof overclothes waterproof trousers