Knapsack problem/Bounded: Difference between revisions

 

This is the list:

|+ Table of potential knapsack items

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

*   [[Knapsack problem/0-1]]

<br><br>

 

=={{header|AutoHotkey}}==

iterative dynamic programming solution

,camera,tshirt,trousers,umbrella,waterproof trousers,waterproof overclothes,notecase

,sunglasses,towel,socks,book

}

 

 

=={{header|Bracmat}}==

( things

= (map.9.150.1)

);

 

{{out}}

<pre> 1010

=={{header|C}}==

 

#include <stdlib.h>

 

return 0;

}

 

{{output}}

socks 1 4 50

count, weight, value: 14 396 1010</pre>

 

=={{header|C++}}==

C++ DP solution. Initially taken from C but than fixed and refactored.<br>

Remark: The above comment implies there is a bug in the C code, but refers to a much older and very different version [[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 19:28, 20 March 2017 (UTC)

#include <vector>

#include <algorithm>

cout << "Weight: " << solution.w << " Value: " << solution.v << endl;

return 0;

 

=={{header|Clojure}}==

We convert the problem to a Knapsack-0/1 problem by replacing (n-max item) vith n-max identical occurences of 1 item.

Adapted Knapsack-0/1 problem solution from [https://www.rosettacode.org/wiki/Knapsack_problem/0-1#Clojure]

(:gen-class))

 

(println "Total value:" value)

(println "Total weight:" (reduce + (map (comp :weight items) indexes))))

{{Output}}

<pre>

Total weight: 396

</pre>

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

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

 

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

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

 

=={{header|D}}==

{{trans|Python}}

Solution with memoization.

 

immutable struct Item {

 

writeln("Total weight: ", w, " Value: ", v_lst[0]);

{{out}}

<pre>1 map

=={{header|EchoLisp}}==

We convert the problem to a Knapsack-0/1 problem by replacing (n-max item) vith n-max identical occurences of 1 item.

(lib 'struct)

(lib 'sql)

(name i))))

 

{{out}}

(define goodies

'((map 9 150 1) (compass 13 35 1)(water 153 200 3)

(length (hash-keys H))

→ 10827 ;; # of entries in cache

 

=={{header|Go}}==

Solution with caching.

 

import "fmt"

}

fmt.Printf("Value: %d; weight: %d\n", v, w)

(A simple test and benchmark used while making changes to make sure performance wasn't sacrificed is available at [[/Go_test]].)

{{out}}

=={{header|Groovy}}==

Solution: dynamic programming

def totalValue = { list -> list.collect{ it.item.value * it.count }.sum() }

 

}

m[n][400]

Test:

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

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

printf (' item: %-22s weight:%4d value:%4d count:%2d\n',

it.item.name, it.item.weight, it.item.value, it.count)

{{out}}

<pre>Elapsed Time: 0.603 s

=={{header|Haskell}}==

Directly lifted from 1-0 problem:

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

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

new = map (\(val,itms)->(val + v * i, (name,i):itms)) old

 

{{out}}

 

</pre>

The above uses merging lists for cache. It's faster, and maybe easier to understand when some constant-time lookup structure is used for cache (same output):

 

-- snipped the item list; use the one from above

prepend (x,n) (y,s) = (x+y,n:s)

 

 

=={{header|J}}==

Brute force solution:

'map'; 9 150 1

'compass'; 13 35 1

 

bestCombo''

Interpretation of answer:

1 1 1 0 2 0 3 0 1 0 1 0 0 0 0 0 1 1 1 0 1 0

(0<decode 978832641) # (":,.decode 978832641),.' ',.names

396

values +/ .* decode 978832641

Dynamic programming solution (faster):

m=. 0$~1+400,+/pieces NB. maximum value cache

b=. m NB. best choice cache

 

dyn''

Note: the brute force approach would return multiple "best answers" if more than one combination of choices would satisfy the "best" constraint. The dynamic approach arbitrarily picks one of those choices. That said, with this particular choice of item weights and values, this is an irrelevant distinction.

 

=={{header|Java}}==

General dynamic solution after [[wp:Knapsack_problem#0-1_knapsack_problem|wikipedia]]. The solution extends the method of [[Knapsack problem/0-1#Java ]].

 

import hu.pj.alg.BoundedKnapsack;

new BoundedKnapsackForTourists();

}

 

import hu.pj.obj.Item;

setInitialStateForCalculation();

}

 

import hu.pj.obj.Item;

solutionWeight = 0;

}

 

public class Item {

public int getInKnapsack() {return inKnapsack;}

public int getBounding() {return bounding;}

{{out}}

<pre>

=={{header|JavaScript}}==

Based on the (dynamic) J implementation. Expressed as an htm page:

 

<script type="text/javascript">

}

findBestPack();

This will generate (translating html to mediawiki markup):

{|

Total weight: 396<br>

Total value: 1010

 

=={{header|Julia}}==

The solution uses Julia's [https://github.com/JuliaOpt/MathProgBase.jl MathProgBase]. Most of the work is done with this package's <code>mixintprog</code> function.

 

 

weight::T

value::T

quant::T

end

 

else

for (i, g) in enumerate(gear)

push!(pack, KPDSupply(g.item, g.weight, g.value, s[i]))

end

return pack

end

 

KPDSupply("compass", 13, 35, 1),

KPDSupply("water", 153, 200, 2),

 

pack = solve(gear, 400)

 

 

{{out}}

<pre>

</pre>

 

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

{0, #[[4]]} & /@ #, Integers]} &@{{"map", 9, 150, 1},

{"towel", 18, 12, 2},

{"socks", 4, 50, 1},

{{Out}}

<pre>{{"map", 1}, {"compass", 1}, {"water", 1}, {"sandwich",

 

=={{header|Mathprog}}==

This model finds the integer optimal packing of a knapsack

;

 

 

The solution produced using glpk is here: [[Knapsack problem/Bounded/Mathprog]]

 

The constraints may be found here: [[:File:Knap_constraint.png]]

 

=={{header|OOCalc}}==

 

=={{header|OxygenBasic}}==

type KnapSackItem string name,sys dag,value,tag

 

'

'Weight: 396

 

=={{header|Oz}}==

Using constraint programming.

%% maps items to tuples of

%% Weight(hectogram), Value and available Pieces

{System.printInfo "\n"}

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

{{out}}

<pre>

</pre>

Takes about 3 seconds on a slow netbook.

 

=={{header|Perl}}==

Recursive solution with caching.

 

use strict;

}

}

{{out}}

<pre>1 of map

1 of socks

Value: 1010; Weight: 396</pre>

 

=={{header|Phix}}==

===Very dumb and very slow brute force version===

Of no practical use, except for comparison against improvements.

{{out}}

<pre>

Much faster but limited to integer weights

{{trans|C}}

{{out}}

<pre>

would obviously increase dramatically. A naive cache could also suffer similarly, if it retained

duplicate solutions for w=15.783, 15.784, 15.785, and everything in between.

{{out}}

<pre>

</pre>

Even on this simple integer-only case, range cache reduces cache size better than 10-fold and effort 6-fold.<br>

<pre>

Value 1010, weight 396 [18.14s]

cache_entries:0, hits:0, misses:33615741

</pre>

 

=={{header|PicoLisp}}==

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

("water" 153 200 3) ("sandwich" 50 60 2)

(for I K

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

{{out}}

<pre> map 9 150

{{libheader|clpfd}}

Library clpfd is written by <b>Markus Triska</b>. Takes about 3 seconds to compute the best solution.

 

% tuples (name, weights, value, nb pieces).

sformat(W3, A3, [V]),

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

{{out}}

<pre> ?- knapsack.

===Library simplex===

Library simplex is written by <b>Markus Triska</b>. Takes about 10 seconds to compute the best solution.

% tuples (name, weights, value, pieces).

knapsack :-

W2 is W1 + X * W,

V2 is V1 + X * V),

 

=={{header|Python}}==

Not as [[Knapsack problem/0-1#Python|dumb a search]] over all possible combinations under the maximum allowed weight:

from collections import namedtuple

 

' All combinations below the maxwt '

if not items:

else:

this, *items = items # car, cdr

if w > maxwt:

break

 

maxwt = 400

) ]

 

{{out}}

<pre>Bagged the following 14 items

===Dynamic programming solution===

This is much faster. It expands the multiple possible instances of an item into individual instances then applies the zero-one dynamic knapsack solution:

 

try:

for item,grp in groupby(sorted(bagged))))

print("for a total value of %i and a total weight of %i" % (

===Non-zero-one solution===

 

#cache: could just use memoize module, but explicit caching is clearer

def choose_item(weight, idx, cache):

if idx < 0: return 0, []

k = (weight, idx)

if k in cache: return cache[k]

best_v, best_list = 0, []

for i in range(0, qty + 1):

wlim = weight - i * w

if wlim < 0: break

val, taken = choose_item(wlim, idx - 1, cache)

if val + i * v > best_v:

best_v = val + i * v

best_list = taken[:]

cache[k] = [best_v, best_list]

return best_v, best_list

v, lst = choose_item(400, len(items) - 1, {})

w = 0

if cnt > 0:

 

 

=={{header|Racket}}==

The algorithm is nearly a direct translation of Haskell's array-based implementation. However, the data is taken from the webpage itself.

 

#lang racket

(require net/url html xml xml/path)

(match-let ([(solution value choices) (best (vector->list (solution-vector capacity)))])

(solution value (filter (compose positive? choice-count) choices))))

 

{{out}}

(choice "map" 1)))

</pre>

 

=={{header|REXX}}==

<br>"unrolled" and converted into discrete combination checks (based on the number of items). &nbsp; The unused combinatorial

<br>checks were discarded and only the pertinent code was retained.

call @gen /*generate items and initializations. */

call @sort /*sort items by decreasing their weight*/

do j37=j36+(j36>0) to h;if w.j37+w36>m then iterate j36;w37=w36+w.j37;z37=z36+v.j37;if z37>$ then call j? 37

end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end

'''output'''

<pre>

{{trans|Python}}

 

# Item struct to represent each item in the problem

Struct.new('Item', :name, :weight, :value, :count)

 

p "Total weight: #{w}, Value: #{val}"

 

=={{header|SAS}}==

 

Use MILP solver in SAS/OR:

data mydata;

input item $1-23 weight value pieces;

print TotalValue;

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

 

Output:

=={{header|Sidef}}==

{{trans|Perl}}

map 9 150 1

compass 13 35 1

say "#{p[i]} of #{items[i].name}" if p[i].is_pos

}

{{out}}

<pre>

1 of socks

Value: 1010; Weight: 396

</pre>

 

=={{header|Tcl}}==

Classic dumb search algorithm:

set items {

{map 9 150 1}

foreach {count item} [countednames $best] {

puts "\t$count * $item"

{{out}}

<pre>

Instead of an ''ad-hoc'' solution, we can convert this task to a

[[wp:Mixed_integer_programming#Integer_unknowns|mixed integer programming]] problem instance and solve it with the [http://lpsolve.sourceforge.net lpsolve] library, which is callable in Ursala.

#import flo

#import lin

#show+

 

The <code>linear_system$[</code>...<code>]</code> function takes the item list as an argument and returns a data structure with the following fields, which is passed to the <code>solution</code> function, which calls the <code>lpsolve</code> routines.

* <code>integers</code> declares that all variables in the list take integer values

1 water

1 waterproof overclothes</pre>

 

=={{header|zkl}}==

{{trans|Haskell}}

[1..c].reduce(fcn(list,i,nm,w,v,old){

wi,left,right:=w*i,list[0,wi],list[wi,*];

fcn([(v1,_)]a,[(v2,_)]b){ v1>v2 and a or b },new));

},old,nm,w,v,old);

T("apple", 39, 40,3),T("banana", 27,60,3),

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

'wrap(nm,n){ items[items.filter1n(fcn(it,nm){ it[0]==nm },nm)][1]*n })

.sum(0)

knapsack:=items.reduce(addItem,(MAX_WEIGHT).pump(List,T(0,T).copy))[-1];

{{out}}

<pre>