Knapsack problem/0-1: Difference between revisions

{{task|Classic CS problems and programs}}

{{omit from|GUISS}}

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 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 trip.

 

 

|+ Table of potential knapsack items

|- style="background-color: rgb(255, 204, 255);"

|}

 

The tourist can choose to take any combination of items from the list,

but only one of each item is available.

He may not cut or diminish the items, so he can only take whole units of any item.

 

 

[dag = decagram = 10 grams]

 

 

=={{header|Ada}}==

with Ada.Strings.Unbounded;

 

end if;

end loop;

{{out}}

<pre>

 

=={{header|APL}}==

[1] total←400

[2] list←("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)

[10] :end

[11] ret←⊃ret,⊂'TOTALS:' (+/2⊃¨ret)(+/3⊃¨ret)

{{out}}

<pre>

 

Average runtime: 0.000168 seconds

</pre>

 

=={{header|BBC BASIC}}==

{{works with|BBC BASIC for Windows}}

nItems% = 22

maxWeight% = 400

m{(index%)} = excluded{}

ENDIF

{{out}}

<pre>

 

=={{header|Bracmat}}==

( things

= (map.9.150)

& out$(!maxvalue.!sack));

{{out}}

. map

compass

note-case

sunglasses

 

=={{header|C}}==

#include <stdlib.h>

 

typedef struct {

} item_t;

 

};

 

}

 

}

}

{{out}}

<pre>

</pre>

 

{{libheader|System}}

{{libheader|System.Collections.Generic}}

using System.Collections.Generic;

 

}

}

("Bag" might not be the best name for the class, since "bag" is sometimes also used to refer to a multiset data structure.)

 

=={{header|Clojure}}==

Uses the dynamic programming solution from [[wp:Knapsack_problem#0-1_knapsack_problem|Wikipedia]].

First define the ''items'' data:

[ "map" 9 150

"compass" 13 35

(defstruct item :name :weight :value)

 

''m'' is as per the Wikipedia formula, except that it returns a pair ''[value indexes]'' where ''indexes'' is a vector of index values in ''items''. ''value'' is the maximum value attainable using items 0..''i'' whose total weight doesn't exceed ''w''; ''indexes'' are the item indexes that produces the value.

 

(defn m [i w]

no))))))

 

Call ''m'' and print the result:

 

(let [[value indexes] (m (-> items count dec) 400)

(println "items to pack:" (join ", " names))

(println "total value:" value)

{{out}}

<pre>items to pack: map, compass, water, sandwich, glucose, banana, suntan cream, waterproof trousers,

=={{header|Common Lisp}}==

Cached method.

(defmacro mm-set (p v) `(if ,p ,p (setf ,p ,v)))

 

(T-shirt 24 15) (trousers 48 10) (umbrella 73 40)

(trousers 42 70) (overclothes 43 75) (notecase 22 80)

{{out}}

<pre>(1030 396

(BANANA 27 60) (CREAM 11 70) (TROUSERS 42 70) (OVERCLOTHES 43 75)

(NOTECASE 22 80) (GLASSES 7 20) (SOCKS 4 50)))</pre>

 

=={{header|D}}==

===Dynamic Programming Version===

{{trans|Python}}

 

struct Item { string name; int weight, value; }

const t = reduce!q{ a[] += [b.weight, b.value] }([0, 0], bag);

writeln("\nTotal weight and value: ", t[0] <= limit ? t : [0, 0]);

{{out}}

<pre>Items:

===Brute Force Version===

{{trans|C}}

 

immutable Item[] items = [

}

writefln("\nTotal value: %d; weight: %d", s.value, w);

The runtime is about 0.09 seconds.

{{out}}

===Short Dynamic Programming Version===

{{trans|Haskell}}

 

struct Item { string name; int w, v; }

void main() {

reduce!addItem(Pair().repeat.take(400).array, items).back.writeln;

Runtime about 0.04 seconds.

{{out}}

<pre>Tuple!(int, "tot", string[], "names")(1030, ["banana", "compass", "glucose", "map", "note-case", "sandwich", "socks", "sunglasses", "suntan cream", "water", "overclothes", "waterproof trousers"])</pre>

 

=={{header|Dart}}==

int MIN_VALUE=-100;

int N = items.length; // number of items

print("Elapsed Time = ${sw.elapsedInMs()}ms");

{{out}}

<pre>[item, profit, weight]

Total Weight = 396

Elapsed Time = 6ms</pre>

 

=={{header|EchoLisp}}==

(require 'struct)

(require 'hash)

(set! restant (- restant (poids i)))

(name i)))

{{out}}

;; init table

(define goodies

(length (hash-keys H))

→ 4939 ;; number of entries "i | weight" in hash table

 

=={{header|Eiffel}}==

class

APPLICATION

 

end

class

ITEM

 

end

class

KNAPSACKZEROONE

 

end

{{out}}

<pre>

compass

map

</pre>

 

{{Trans|Common Lisp}} with changes (memoization without macro)

 

(defun ks (max-w items)

(let ((cache (make-vector (1+ (length items)) nil)))

(waterproof-trousers 42 70) (overclothes 43 75) (notecase 22 80)

(glasses 7 20) (towel 18 12) (socks 4 50) (book 30 10)))

 

{{out}}

 

Another way without cache :

(defun best-rate (l1 l2)

"predicate for sorting a list of elements regarding the value/weight rate"

(waterproof-trousers 42 70) (overclothes 43 75) (notecase 22 80)

(glasses 7 20) (towel 18 12) (socks 4 50) (book 30 10)) 400)

 

{{out}} with org-babel in Emacs

| | 396 | 1030 |

 

</pre>

 

=={{header|Euler Math Toolbox}}==

 

>items=["map","compass","water","sandwich","glucose", ...

> "tin","banana","apple","cheese","beer","suntan creame", ...

sunglasses

socks

 

=={{header|Factor}}==

Using dynamic programming:

math.order math.parser math.ranges sequences sorting ;

IN: rosetta.knappsack.0-1

"Items packed: " print

natural-sort

<pre>

( scratchpad ) main

 

=={{header|Forth}}==

\ Rosetta Code Knapp-sack 0-1 problem. Tested under GForth 0.7.3.

\ 22 items. On current processors a set fits nicely in one CELL (32 or 64 bits).

." Weight: " Sol @ [ END-SACK Sack ]sum . ." Value: " Sol @ [ END-SACK VAL + Sack VAL + ]sum .

;

{{out}}

<pre>

socks

Weight: 396 Value: 1030

</pre>

 

=={{header|Go}}==

From WP, "0-1 knapsack problem" under [http://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_Programming_Algorithm|Solving The Knapsack Problem], although the solution here simply follows the recursive defintion and doesn't even use the array optimization.

 

import "fmt"

{"book", 30, 10},

}

 

func main() {

fmt.Println(items)

fmt.Println("weight:", w)

}

return i0, w0, v0

{{out}}

<pre>

weight: 396

value: 1030

</pre>

 

=={{header|Groovy}}==

Solution #1: brute force

def totalValue = { list -> list*.value.sum() }

350 < w && w < 401

}.max(totalValue)

Solution #2: dynamic programming

def n = possibleItems.size()

def m = (0..n).collect{ i -> (0..400).collect{ w -> []} }

}

m[n][400]

Test:

[name:"map", weight:9, value:150],

[name:"compass", weight:13, value:35],

printf (" item: %-25s weight:%4d value:%4d\n", it.name, it.weight, it.value)

}

{{out}}

<pre>Elapsed Time: 132.267 s

=={{header|Haskell}}==

Brute force:

("glucose",15,60), ("tin",68,45), ("banana",27,60), ("apple",39,40),

("cheese",23,30), ("beer",52,10), ("cream",11,70), ("camera",32,30),

putStr "Total value: "; print value

mapM_ print items

{{out}}

<pre>

</pre>

Much faster brute force solution that computes the maximum before prepending, saving most of the prepends:

("glucose",15,60), ("tin",68,45), ("banana",27,60), ("apple",39,40),

("cheese",23,30), ("beer",52,10), ("cream",11,70), ("camera",32,30),

skipthis = combs rest cap

 

{{out}}

<pre>(1030,[("map",9,150),("compass",13,35),("water",153,200),("sandwich",50,160),("glucose",15,60),("banana",27,60),("cream",11,70),("trousers",42,70),("overclothes",43,75),("notecase",22,80),("sunglasses",7,20),("socks",4,50)])</pre>

 

Dynamic programming with a list for caching (this can be adapted to bounded problem easily):

("glucose",15,60), ("tin",68,45), ("banana",27,60), ("apple",39,40),

("cheese",23,30), ("beer",52,10), ("cream",11,70), ("camera",32,30),

(left,right) = splitAt w list

 

{{out}}

(1030,["map","compass","water","sandwich","glucose","banana","cream","waterproof trousers","overclothes","notecase","sunglasses","socks"])

=={{header|Icon}} and {{header|Unicon}}==

Translation from Wikipedia pseudo-code. Memoization can be enabled with a command line argument that causes the procedure definitions to be swapped which effectively hooks the procedure.

 

global wants # items wanted for knapsack

packing(["socks"], 4, 50),

packing(["book"], 30, 10) ]

{{libheader|Icon Programming Library}}

[http://www.cs.arizona.edu/icon/library/src/procs/printf.icn printf.icn provides printf]

=={{header|J}}==

Static solution:

'map'; 9 150

'compass'; 13 35

X=: +/ .*"1

plausible=: (] (] #~ 400 >: X) #:@i.@(2&^)@#)@:({."1)

Illustration of answer:

396 1030

best#names

notecase

sunglasses

 

=={{header|Java}}==

General dynamic solution after [[wp:Knapsack_problem#0-1_knapsack_problem|wikipedia]].

 

import hu.pj.alg.ZeroOneKnapsack;

}

 

 

import hu.pj.obj.Item;

}

 

 

public class Item {

public int getBounding() {return bounding;}

 

{{out}}

<pre>

=={{header|JavaScript}}==

Also available at [https://gist.github.com/truher/4715551|this gist].

/*

* 0-1 knapsack solution, recursive, memoized, approximate.

12

]);

 

=={{header|jq}}==

corresponding to no items). Here, m[i,W] is set to [V, ary]

where ary is an array of the names of the accepted items.

# Because of the way addition is defined on null and because of the

# way setpath works, there is no need to initialize the matrix m in

.[$i][$j] = .[$i-1][$j]

end))

'''Example''':

{name: "map", "weight": 9, "value": 150},

{name: "compass", "weight": 13, "value": 35},

];

 

{{out}}

1030

 

=={{header|Julia}}==

<code>KPDSupply</code> has one more field than is needed, <code>quant</code>. This field is may be useful in a solution to the bounded version of this task.

 

weight::T

value::T

quant::T

end

 

 

KPDSupply("compass", 13, 35),

KPDSupply("water", 153, 200),

 

pack = solve(gear, 400)

 

 

{{out}}

<pre>

</pre>

 

=={{header|LSL}}==

To test it yourself, rez a box on the ground, add the following as a New Script, create a notecard named "Knapsack_Problem_0_1_Data.txt" with the data shown below.

integer iMAX_WEIGHT = 400;

integer iSTRIDE = 4;

}

}

Notecard:

<pre>map, 9, 150

iTotalValue=1030</pre>

 

Used the

Position[LinearProgramming[-#[[;; , 3]], -{#[[;; , 2]]}, -{400},

{0, 1} & /@ #, Integers], 1], 1]] &@

{"towel", 18, 12},

{"socks", 4, 50},

{{Out}}

<pre>{"map", "compass", "water", "sandwich", "glucose", "banana", "suntan cream", "waterproof trousers", "waterproof overclothes", "note-case", "sunglasses", "socks"}</pre>

 

=={{header|Mathprog}}==

This model finds the integer optimal packing of a knapsack

;

 

The solution may be found at [[Knapsack problem/0-1/Mathprog]].

Activity=1 means take, Activity=0 means don't take.

 

=={{header|MAXScript}}==

global globalItems = #()

global usedMass = 0

)

format "Total mass: %, Total Value: %\n" usedMass totalValue

{{out}}

Item name: water, weight: 153, value:200

Item name: sandwich, weight: 50, value:160

Total mass: 396, Total Value: 1030

OK

 

=={{header|OCaml}}==

A brute force solution:

"map", 9, 150;

"compass", 13, 35;

(List.hd poss) (List.tl poss) in

List.iter (fun (name,_,_) -> print_endline name) res;

 

=={{header|Oz}}==

Using constraint programming.

%% maps items to pairs of Weight(hectogram) and Value

Problem = knapsack('map':9#150

{System.printInfo "\n"}

{System.showInfo "total value: "#{Value Best}}

{{out}}

<pre>

</pre>

Typically runs in less than 150 milliseconds.

 

=={{header|Perl}}==

The dynamic programming solution from Wikipedia.

map 9 150

compass 13 35

my (@name, @weight, @value);

for (split "\n", $raw) {

}

 

my $max_weight = 400;

 

sub optimal {

 

 

}

}