Knapsack problem/0-1: Difference between revisions

{{trans|Python}}

 

V totwt = 0

V totval = 0

print("Bagged the following items\n "sorted(bagged.map((item, _, _2) -> item)).join("\n "))

V (val, wt) = totalvalue(bagged)

 

{{out}}

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

 

=={{header|AWK}}==

# syntax: GAWK -f KNAPSACK_PROBLEM_0-1.AWK

BEGIN {

exit(0)

}

{{out}}

<pre>

{{works with|QuickBasic|4.5}}

{{trans|QB64}}

RANDOMIZE TIMER

DIM L(N), C(N), j(N), q(a), d(a), q$(a)

IF d(i) <= G AND q(i) > max THEN max = q(i): h = i

NEXT i

{{out}}

<pre>Same as QB64 entry.</pre>

==={{header|Yabasic}}===

{{trans|QB64}}

dim L(N), C(N), j(N), q(a), d(a), q$(a)

 

next i

print d(h), chr$(9), q(h), chr$(9), q$(h)

{{out}}

<pre>Same as QB64 entry

 

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

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

 

Random values origin are automatically assigned create integral of quantity and quality

 

using System.Text; // rextester.com/YRFA61366

namespace Knapsack

}

}

 

{{out}}

=== First version ===

{{libheader|Boost}}

#include <string>

#include <iostream>

bestItems.swap( solutionSets[ n - 1][ weightlimit - 1 ] ) ;

return bestValues[ n - 1 ][ weightlimit - 1 ] ;

{{out}}

<pre>

=== Second version ===

{{Works with|C++17}}

#include <iostream>

#include <set>

std::cout << std::endl << std::setw(24) << "total:" << std::setw(6) << totalweight << std::setw(6) << bestValue << std::endl;

return 0;

{{Out}}

<pre> best knapsack:

=={{header|C_sharp}}==

All combinations, eight threads, break when weight is to large.

using System.Threading.Tasks;

class Program

"waterproof trousers","waterproof overclothes",

"note-case","sunglasses","towel","socks","book"};

A dynamic version.

class program

{

"waterproof trousers","waterproof overclothes",

"note-case","sunglasses","towel","socks","book"};

 

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

=={{header|Crystal}}==

Branch and bound solution

 

struct BitArray

puts "total weight #{used.sum(&.weight)}, total value #{used.sum(&.value)}"

puts "checked nodes: #{solver.checked_nodes}"

{{out}}

<pre>optimal choice: ["map", "socks", "suntan cream", "glucose", "note-case", "sandwich", "sunglasses", "compass", "banana", "waterproof overclothes", "waterproof trousers", "water"]

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

 

=={{header|Dart}}==

int MIN_VALUE=-100;

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

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

{{out}}

<pre>[item, profit, weight]

 

=={{header|EasyLang}}==

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 160 60 45 60 40 30 10 70 30 15 10 40 70 75 80 20 12 50 10 ]

for i range len items[]

print " " & name$[items[i]]

 

=={{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|F_Sharp|F#}}==

===Using A* Algorithm===

//Solve Knapsack 0-1 using A* algorithm

//Nigel Galloway, August 3rd., 2018

if bv>=h then t else fN (fH zl (bv,t) zw zv zt)

fN (fH 0 (0.0,[]) 0.0 0.0 [])

{{out}}

let itemsf = [

"map", 9.0, 150.0;

"socks", 4.0, 50.0;

"book", 30.0, 10.0;]|> List.sortBy(fun(_,n,g)->n/g)

<pre>

> let x=knapStar itemsf 400.0;;

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

=={{header|FreeBASIC}}==

{{trans|XPL0}}

Dim As Integer i, A, P, V, N

Dim As Integer MejorArticulo, MejorValor = 0

Wend

Print "Totals:"; Spc(25); P; Tabu; V

{{out}}

<pre>Same as XLP0 entry.</pre>

 

=={{header|FutureBasic}}==

 

_maxWeight = 400

fn FillKnapsack

 

 

{{output}}

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

 

'''Type and Functions''':

item::String

weight::T

sol = mixintprog(-v, w', '<', capacity, :Bin, 0, 1, CbcSolver())

gear[sol.sol .≈ 1]

 

'''Main''':

KPDSupply("compass", 13, 35),

KPDSupply("water", 153, 200),

println("The hicker should pack: \n - ", join(pack, "\n - "))

println("\nPacked weight: ", mapreduce(x -> x.weight, +, pack), " kg")

 

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

=={{Header|Lua}}==

This version is adapted from the Clojure version.

{"map", 9, 150},

{"compass", 13, 35},

for k,v in pairs(memo) do count = count + 1 end

printf("\n(memo count: %d; mm call count: %d)", count, mm_calls)

 

{{out}}

</pre>

=={{header|Maple}}==

vals := [150,35,200,160,60,45,60,40,30,10,70,30,15,10,40,70,75,80,20,12,50,10]:

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"]:

end if:

end do:

{{Out}}

<pre>Total Value is 1030

=={{header|Mathematica}}/{{header|Wolfram Language}}==

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

%Knapsack 0/1. Nigel Galloway: October 5th., 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};

solve maximize wValue;

output["Take "++show(take)++"\nTotal Weight=\(wTaken) Total Value=\(wValue)"]

{{out}}

<pre>

:– use a cache for memoization.

 

# Knapsack. Recursive algorithm.

 

echo "Total weight: ", weight

echo "Total value: ", value

 

{{out}}

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

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

readln;

end.

 

Output

=={{header|Perl}}==

The dynamic programming solution from Wikipedia.

map 9 150

compass 13 35

 

my $solution = optimal($#name, $max_weight);

{{out}}

<pre>1030: map compass water sandwich glucose banana suntancream waterproof trousers waterproof overclothes note-case sunglasses socks</pre>

=={{header|Phix}}==

Trivial simplification of the [[Knapsack_problem/Bounded#Phix|Knapsack/Bounded]] solution. By careful ordering we can ensure we find the optimal solution first (see terminate flag).

<span style="color: #000080;font-style:italic;">-- demo\rosetta\knapsack0.exw</span>

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

{{out}}

<pre>

 

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

 

=={{header|Picat}}==

 

go =>

["socks", 4, 50],

["book", 30, 10]],

 

{{out}}

 

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

 

Program write results to qb64 directory

N=7: L=5: a = 2^(N+1): Randomize Timer 'knapsack.bas DANILIN

Dim L(N), C(N), j(N), q(a), q$(a), d(a)

If d(i)<=L Then If q(i) > max Then max=q(i): m=i

Next

 

Main thing is very brief and clear to even all<br/><br/>

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

return sum([x[2] for x in items]) if sum([x[1] for x in items]) <= max_weight else 0

print x[0]

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

 

 

Random values origin are automatically assigned create integral of quantity and quality

 

L=[];C=[];e=[];j=[];q=[];s=[] # rextester.com/BCKP19591

d=[];L=[1]*n;C=[1]*n;e=[1]*a

if d[i]<=G and q[i]>max:

max=q[i]; m=i

{{out}}

<pre># Mass Cost

 

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

 

=={{header|Racket}}==

#lang racket

; An ITEM a list of three elements:

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

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

{{out}}

'(1030 396 (map compass water sandwich glucose banana cream trousers overclothes notecase glasses socks))

Brute Force and Memoized Recursive Alternate

#lang racket

 

'value: (pack-value pack)

'items: (map car pack))))

Brute Force

(define (show-brute)

 

 

(show-brute); takes around five seconds on my machine

Recursive Alternate

(define (show-memoized)

 

 

(show-memoized)

 

{{out}}

(weight: 396 value: 1030 items: (map compass water sandwich glucose banana cream trousers overclothes notecase glasses socks))

 

=={{header|Raku}}==

==== Brute force ====

{{works with|Rakudo|2017.01}}

 

multi sub pokem ([], $, $v = 0) { $v }

 

my ($value, @result) = pokem @table, $MAX_WEIGHT;

{{out}}

<pre>Value = 1030

Much faster than the previous example.

{{trans|Perl}}

map 9 150

compass 13 35

 

my @solution = optimal(@name.end, $sum);

{{out}}

<pre>1030: banana, compass, glucose, map, note-case, sandwich, socks, sunglasses, suntancream, water, waterproof overclothes, waterproof trousers

 

The term &nbsp; ''allowable items'' &nbsp; refers to all items that are of allowable weight (those that weigh within the weight criteria). &nbsp; An half metric─ton anvil was added to the list to show how overweight items are pruned from the list of items.

maxWeight=400 /*the maximum weight for the knapsack. */

say 'maximum weight allowed for a knapsack:' commas(maxWeight); say

end /*k*/

end /*j*/ /* [↑] sort choices by decreasing wt. */

{{out|output|text=&nbsp; when using the default input:}}

<pre>

=={{header|Ruby}}==

=== Brute force ===

potential_items = [

KnapsackItem['map', 9, 150], KnapsackItem['compass', 13, 35],

puts "weight: #{wt}"

puts "items: #{items.join(',')}"

 

{{out}}

=== Dynamic Programming ===

Translated from http://sites.google.com/site/mikescoderama/Home/0-1-knapsack-problem-in-p

 

def dynamic_programming_knapsack(items, max_weight)

puts "total weight: #{weight}"

puts "total value: #{value}"

{{out}}

<pre style='width: full; overflow: scroll'>

=={{header|Rust}}==

Dynamic Programming solution.

 

struct Item {

println!("Total weight: {}", items.iter().map(|w| w.weight).sum::<usize>());

println!("Total value: {}", items.iter().map(|w| w.value).sum::<usize>());

{{out}}

<pre>map

 

Use MILP solver in SAS/OR:

data mydata;

input item $1-23 weight value;

print TotalValue;

print {i in ITEMS: NumSelected[i].sol > 0.5} NumSelected;

 

Output:

=={{header|Scala}}==

{{works with|Scala|2.9.2}}

 

case class Item(name: String, weight: Int, value: Int)

println(" elapsed time: "+t+" sec"+"\n")

}

{{out}}

<pre>packing list of items (brute force):

=={{header|Sidef}}==

{{trans|Perl}}

map, 9, 150

compass, 13, 35

 

var sol = optimal(items.end, max_weight)

{{out}}

<pre>

Displays the top 5 solutions and runs in about 39 seconds.

 

WITH KnapsackItems (item, [weight], value) AS

(

GO

DROP TABLE #KnapsackItems;

{{out}}

<pre>

=== Dynamic Programming ===

 

var name: String

var weight: Int

let (tValue, tWeight) = kept.reduce((0, 0), { ($0.0 + $1.value, $0.1 + $1.weight) })

 

 

{{out}}

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

set items {

{map 9 150}

# Pretty-print the results

puts "Best filling has weight of [expr {[weight $best]/100.0}]kg and score [value $best]"

{{out}}

<pre>

=={{header|Ursala}}==

This solution follows a very similar approach to the one used in [[Knapsack problem/Bounded#Ursala]], which is to treat it as a mixed integer programming problem and solve it using an off-the-shelf library ([http://lpsolve.sourceforge.net lpsolve]).

#import nat

#import flo

#show+

 

Binary valued variables are a more specific constraint than the general mixed integer programming problem, but can be accommodated as shown using the <code>binaries</code> field in the <code>linear_system</code> specification. The additional <code>slack</code> variable is specified as continuous and non-negative with no cost or benefit so as to make the constraint equation solvable without affecting the solution.

{{out}}

 

=={{header|VBA}}==

Option Explicit

Const maxWeight = 400

Call ChoiceBin(n + 1, ss)

End If

{{out}}

<pre>

=={{header|VBScript}}==

Non recurvive unfolded force version. Created by an other script. It runs 13 times faster than the recursive one.

dim w(22),v(22),m(22)

data=array( "map", 9, 150, "compass", 13, 35, "water", 153, 200, _

if l(i)=1 then wlist=wlist&vbCrlf&data((i-1)*3)

next

{{out}}

<pre>

=={{header|Visual Basic}}==

{{works with|Visual Basic|VB6 Standard}}

Option Explicit

Const maxWeight = 400

Call ChoiceBin(n + 1, ss)

End If

{{out}}

<pre>

=={{header|Visual Basic .NET}}==

{{works with|Visual Basic .NET|2013}}

Public Class KnapsackBin

Const knam = 0, kwei = 1, kval = 2

 

End Class 'KnapsackBin

{{out}}

<pre>

=={{header|Vlang}}==

{{trans|go}}

name string

w int

}

return i0, w0, v0

{{out}}

<pre>

{{libheader|Wren-fmt}}

Based on the Go example, though modified to give output in tabular form.

 

var wants = [

}

System.print(" --- ----")

 

{{out}}

 

=={{header|XPL0}}==

 

int Item, Items, Weights, Values,

IntOut(0, W); ChOut(0, Tab);

IntOut(0, V); CrLf(0);

 

{{out}}

=={{header|zkl}}==

{{trans|Haskell}}{{trans|D}}

w,left,right:=it[1],pairs[0,w],pairs[w,*];

left.extend(right.zipWith(

fcn([(t1,_)]a,[(t2,_)]b){ t1>t2 and a or b },

pairs.apply('wrap([(tot,names)]){ T(tot + it[2], names + it[0]) })))

T("beer", 52, 10),T("book", 30,10),T("camera", 32, 30),

T("cheese", 23, 30),T("compass", 13,35),T("glucose", 15, 60),

(MAX_WEIGHT).pump(List,T(0,T).copy))[-1]; // nearest to max weight

weight:=items.apply('wrap(it){ knapsack[1].holds(it[0]) and it[1] }).sum(0);

{{out}}

<pre>