Knapsack problem/0-1: Difference between revisions

 

Here is the list:

|+ Table of potential knapsack items

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

*   [[Knapsack problem/Unbounded]]

*   [[Knapsack problem/Continuous]]

<br><br>

 

=={{header|360 Assembly}}==

Non recurvive brute force version.

KNAPSA01 CSECT

USING KNAPSA01,R13

DATAE DC 0C

YREGS

{{out}}

<pre>

 

=={{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|AWK}}==

# syntax: GAWK -f KNAPSACK_PROBLEM_0-1.AWK

BEGIN {

exit(0)

}

{{out}}

<pre>

items=12 (out of 22) weight=396 value=1030

</pre>

 

=={{header|Batch File}}==

:: Initiate command line environment

@echo off

echo Total Value: %totalimportance% Total Weight: %totalweight%

pause>nul

 

{{out}}

=={{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>

 

return 0;

}

{{out}}

<pre>

socks 4 50

totals: 396 1030

</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|Ceylon}}==

<b>module.ceylon</b>:

 

module knapsack "1.0.0" {

}

 

<b>run.ceylon:</b>

 

shared void run() {

value knapsack = pack(items, empty(400));

then packRecursive(sortedItems.rest, add(firstItem,knapsack))

else knapsack;

 

 

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>

=={{header|Elixir}}==

{{trans|Erlang}}

def solve([], _total_weight, item_acc, value_acc, weight_acc), do:

{item_acc, value_acc, weight_acc}

IO.puts "Time elapsed in milliseconds: #{time/1000}"

end

 

{{out}}

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

=={{header|Erlang}}==

 

 

-module(knapsack_0_1).

HeadRes

end.

 

{{out}}

=={{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>

</pre>

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

fn FillKnapsack

 

 

 

 

</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"

}

return i0, w0, v0

{{out}}

<pre>

 

Data for which a greedy algorithm might give an incorrect result:

var wants = []item{

{"sunscreen", 15, 2},

 

const maxWt = 40

{{out}}

<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

 

'''Alternative test case'''

 

'sunscreen'; 15 2

'GPS'; 25 2

X=: +/ .*"1

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

 

Illustration:

 

40 4

best#names

sunscreen

 

=={{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}}

 

 

=={{header|Kotlin}}==

{{trans|Go}}

 

data class Item(val name: String, val weight: Int, val value: Int)

println("---------------------- ------ -----")

println("Total ${chosenItems.size} Items Chosen $totalWeight $totalValue")

 

{{out}}

=={{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|Pascal}}==

Uses a stringlist to store the items. I used the algorithm given on Wikipedia (Knapsack problem) to find the maximum value. It is written in pseudocode that translates very easily to Pascal.

program project1;

uses

const

MaxWeight = 400;

 

type

var

M:TMaxArray;

S,KnapSack:TStringList;

L:string;

begin

//Put all the items into an array called List

S:=TStringList.create;

S.Commatext:=L;

//and recording the value at that point

for j := 0 to MaxWeight do

 

for i := 1 to N do

for j := 0 to MaxWeight do

if List[i].weight > j then

M[i, j] := M[i-1, j]

else

M[i, j] := max(M[i-1, j], M[i-1, j-List[i].weight] + List[i].value);

 

//get the highest total value by testing every value in table M

for i:=1 to N do

for j:= 0 to MaxWeight do

If M[i,j] > MaxValue then

MaxValue := m[i,j];

writeln('Highest total value : ',MaxValue);

 

//Work backwards through the items to find those items that go in the Knapsack (a stringlist)

WeightLeft := MaxWeight;

For i:= N downto 1 do

if M[i,WeightLeft] = MaxValue then

if M[i-1, WeightLeft - List[i].Weight] = MaxValue - List[i].Value then

begin

MaxValue := MaxValue - List[i].Value;

WeightLeft := WeightLeft - List[i].Weight;

 

//Show the items in the knapsack

writeln('-------------------------');

For i:= KnapSack.count-1 downto 0 do

writeln(KnapSack[i]);

 

KnapSack.free;

readln;

end.

 

Output

=={{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 {

 

 

}

}

}

 

{{out}}

 

=={{header|Phix}}==

{{out}}

<pre>

water

</pre>

<pre>

Value 1030, weight 396 [1216430 attempts, 0.84s]:

 

=={{header|PHP}}==

# 0-1 Knapsack Problem Solve with memoization optimize and index returns

# $w = weight of item

}

echo "<tr><td align=right><b>Totals</b></td><td>$totalVal</td><td>$totalWt</td></tr>";

{{out}}

<div class="solutionoutput">

</div>

Minimal PHP Algorithm for totals only translated from Python version as discussed in the YouTube posted video at: http://www.youtube.com/watch?v=ZKBUu_ahSR4

# 0-1 Knapsack Problem Solve

# $w = weight of item

$m3 = knapSolve($w3, $v3, sizeof($v3) -1, 54 );

print_r($w3); echo "<br>";

{{out}}

<pre>

Max: 54 (828 calls)

</pre>

 

=={{header|PicoLisp}}==

("map" 9 150) ("compass" 13 35)

("water" 153 200) ("sandwich" 50 160)

(for I K

(apply tab I (3 -24 6 6) NIL) )

{{out}}

<pre>

===Using the clpfd library===

{{libheader|clpfd}}

 

knapsack :-

sformat(W3, A3, [V]),

format('~w~w~w~n', [W1,W2,W3]),

{{out}}

<pre>

{{libheader|simplex}}

Library written by <b>Markus Triska</b>. The problem is solved in about 3 seconds.

 

knapsack :-

W2 is W1 + W,

V2 is V1 + V),

 

=={{header|PureBasic}}==

Solution uses memoization.

name.s

weight.i ;units are dekagrams (dag)

Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()

CloseConsole()

{{out}}

<pre>

TOTALS: 396 1030

</pre>

 

=={{header|Python}}==

===Brute force algorithm===

 

def anycomb(items):

'\n '.join(sorted(item for item,_,_ in bagged)))

val, wt = totalvalue(bagged)

{{out}}

<pre>

</pre>

=== Dynamic programming solution ===

xrange

except:

'\n '.join(sorted(item for item,_,_ in bagged)))

val, wt = totalvalue(bagged)

===Recursive dynamic programming algorithm===

cache = {}

print x[0]

print "value:", total_value(solution, max_weight)

 

 

 

 

 

{{out}}

 

=={{header|R}}==

Full_Data<-structure(list(item = c("map", "compass", "water", "sandwich",

"glucose", "tin", "banana", "apple", "cheese", "beer", "suntan_cream",

print_output(Full_Data, 400)

 

 

{{out}}

[1] "You must carry: socks"

[2] "You must carry: sunglasses"

[11] "You must carry: compass"

[12] "You must carry: map"