Knapsack problem/0-1: Difference between revisions

 

 

|+ Table of potential knapsack items

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

|}

 

 

 

[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|Bracmat}}==

( things

= (map.9.150)

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

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

 

void AddItem(Item i)

{

items.Add(i);

}

}

}

("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}}==

{{trans|Python}}

 

 

auto tab = new int[][](items.length + 1, limit + 1);

 

tab[i + 1][w] = (it.weight > w) ? tab[i][w] :

max(tab[i][w], tab[i][w - it.weight] + it.value);

 

int w = limit;

if (tab[i + 1][w] != tab[i][w]) {

w -= it.weight;

}

 

enum int limit = 400;

 

{{out}}

 

 

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

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

 

<pre>

(1030 396 ((map 9 150) (compass 13 35) (water 153 200) (sandwich 50 160) (glucose 15 60)

 

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)

 

<pre>

| map | 9 | 150 |

| | 396 | 1030 |

 

</pre>

 

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

waterproof overclothes

waterproof trousers

</pre>

 

=={{header|Go}}==

 

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:

 

 

main = do

<pre>

</pre>

 

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

sunglasses 7 dag (value = 20)

socks 4 dag (value = 50)