Knapsack problem/Unbounded: Difference between revisions

{{task|Classic CS problems and programs}}

 

 

<table

style="text-align: left; width: 80%;" border="4"

cellpadding="2" cellspacing="2"><tr><td

valign="middle">Item</td><td

valign="middle">Explanation</td><td

valign="middle">Value (each)</td><td

valign="middle">weight</td><td

valign="middle">Volume (each)</td></tr><tr><td

align="left" nowrap="nowrap" valign="middle">panacea

nowrap="nowrap" valign="middle">&lt;=25</td><td

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

 

He can only take whole units of any item, but there is much more of any item than he could ever carry

 

 

 

<!-- All solutions

# (9, 0, 11) also minimizes weight and volume within the limits of calculation

-->

 

=={{header|Ada}}==

{{trans|Python}}

 

procedure Knapsack_Unbounded is

Ada.Text_IO.Put_Line ("Ichor: " & Natural'Image (Best_Amounts (2)));

Ada.Text_IO.Put_Line ("Gold: " & Natural'Image (Best_Amounts (3)));

 

=={{header|ALGOL 68}}==

 

[]BOUNTY items = (

name OF items, max items));

printf(($" The weight to carry is "f(d)", and the volume used is "f(d)l$,

<pre>The maximum value achievable (by dynamic programming) is +54500

The number of (panacea, ichor, gold) items to achieve this is: ( 9, 0, 11) respectively

=={{header|AutoHotkey}}==

Brute Force.

Value = 3000,1800,2500

Weight= 3,2,20 ; *10

}

}

 

=={{header|Bracmat}}==

( things

= (panacea.3000.3/10.25/1000)

 

!knapsack;

Output:

<pre>Take 15 items of ichor.

figures out the best (highest value) set by brute forcing every possible subset.

 

#include <stdlib.h>

 

return 0;

}

 

{{output}}<pre>9 panacea

best value: 54500

</pre>

 

=={{header|C_sharp|C#}}==

This model finds the integer optimal packing of a knapsack

}

}

Produces:

<pre>

take(Ichor): 0

take(Gold): 11

</pre>

 

=={{header|Clojure}}==

 

(defn total [key items quantities]

(let [mcw (/ max-weight (:weight item))

mcv (/ max-volume (:volume item))]

We have an <tt>item</tt> struct to contain the data for both contents and the knapsack. The <tt>total</tt> function returns the sum of a particular attribute across all items times their quantities. Finally, the <tt>max-count</tt> function returns the most of that item that could fit given the constraints (used as the upper bound on the combination). Now the real work:

(let [pan (struct item 3000 0.3 0.025)

ich (struct item 1800 0.2 0.015)

i (iters ich)

g (iters gol)]

The <tt>knapsacks</tt> function returns a lazy sequence of all valid knapsacks, with the particular content quantities as metadata. The work of realizing each knapsack is done in parallel via the <tt>pmap</tt> function. The following then finds the best by value, and prints the result.

(reduce #(if (> (:value %1) (:value %2)) %1 %2) ks))

(println "Total weight: " (float w))

(println "Total volume: " (float v))

Calling <tt>(print-knapsack (best-by-value (knapsacks)))</tt> would result in something like:

<pre>Maximum value: 54500

Containing: 9 Panacea, 0 Ichor, 11 Gold</pre>

Further, we could find all "best" knapsacks rather simply (albeit at the cost of some efficiency):

(let [b (best-by-value ks)]

(filter #(= (:value b) (:value %)) ks)))

(doseq [k ks]

(print-knapsack k)

Calling <tt>(print-knapsacks (all-best-by-value (knapsacks)))</tt> would result in something like:

<pre>

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

A dynamic programming <i>O(maxVolume &times; maxWeight &times; nItems)</i> solution, where volumes and weights are integral values.

"Items is a list of lists of the form (name value weight volume) where weight

and value are integers. max-volume and max-weight, also integers, are the

b-items (list* item o-items)))))))

(setf (aref maxes v w)

 

Use, having multiplied volumes and weights as to be integral:

=={{header|D}}==

{{trans|Python}}

import std.stdio, std.algorithm, std.typecons, std.conv;

 

writefln("The weight to carry is %4.1f and the volume used is %5.3f",

best.weight, best.volume);

{{out}}

<pre>Maximum value achievable is 54500

===Alternative Version===

The output is the same.

import std.stdio, std.algorithm, std.typecons, std.range, std.conv;

 

writefln("This is achieved by carrying (one solution) %d panacea, %d ichor and %d gold", best[1][]);

writefln("The weight to carry is %4.1f and the volume used is %5.3f", best[0][1..$]);

 

=={{header|E}}==

This is a mostly brute-force general solution (the first author of this example does not know dynamic programming); the only optimization is that when considering the last (third) treasure type, it does not bother filling with anything but the maximum amount.

 

/** A data type representing a bunch of stuff (or empty space). */

:= makeQuantity( 0, 25, 0.250, [].asMap())

 

 

=={{header|EchoLisp}}==

Use a cache, and multiply by 10^n to get an integer problem.

(require 'struct)

(require 'hash)

→ 218

 

 

=={{header|Eiffel}}==

class

KNAPSACK

 

end

{{out}}

<pre>

This is achieved by carrying 0 panacea, 15 ichor and 11 gold.

The weight is 25 and the volume is 0.247.

</pre>

 

=={{header|Factor}}==

This is a brute force solution. It is general enough to be able to provide solutions for any number of different items.

math.vectors sequences sequences.product combinators.short-circuit ;

IN: knapsack

: best-bounty ( -- bounty )

find-max-amounts [ 1 + iota ] map <product-sequence>

 

=={{header|Forth}}==

: weight cell+ ;

: volume 2 cells + ;

solve-ichor ;

 

Or like this...

0 VALUE ampules

0 VALUE bars

LOOP

LOOP

With the result...

 

{{works with|Fortran|90 and later}}

A straight forward 'brute force' approach

 

IMPLICIT NONE

WRITE(*, "(A,F4.1,A,F5.3)") "The weight to carry is ", totalWeight, " and the volume used is ", totalVolume

Sample output

Maximum value achievable is 54500

This is achieved by carrying 0 panacea, 15 ichor and 11 gold items

The weight to carry is 25.0 and the volume used is 0.247

 

=={{header|Go}}==

Recursive brute-force.

 

import "fmt"

fmt.Printf("TOTAL (%3d items) Weight: %4.1f Volume: %5.3f Value: %6d\n",

sumCount, sumWeight, sumVolume, sumValue)

 

Output:

=={{header|Groovy}}==

Solution: dynamic programming

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

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

}

m[n][wm][vm]

 

Test:

items.eachPermutation { itemList ->

def start = System.currentTimeMillis()

it.item.name, it.count, it.item.weight * it.count, it.item.volume * it.count)

}

 

Output:

=={{header|Haskell}}==

This is a brute-force solution: it generates a list of every legal combination of items (<tt>options</tt>) and then finds the option of greatest value.

import Data.Ord (comparing)

 

 

main = putStr $ showOpt $ best options

 

Output:

 

=={{header|HicEst}}==

 

NN = ALIAS($Panacea, $Ichor, $Gold, wSack, wPanacea, wIchor, wGold, vSack, vPanacea, vIchor, vGold)

ENDDO

ENDDO

value=54500; Panaceas=3; Ichors=10; Golds=11; weight=24.9; volume=0.247;

value=54500; Panaceas=6; Ichors=5; Golds=11; weight=24.8; volume=0.247;

 

=={{header|J}}==

Brute force solution.

prods=: <;. _1 ' panacea: ichor: gold:'

hdrs=: <;. _1 ' weight: volume: value:'

prtscr &.> hdrs ('total '&,@[,' ',":@])&.> mo ip"1 ws,vs,:vls

LF

Example output:

<pre> KS''

=={{header|Java}}==

With recursion for more than 3 items.

 

import hu.pj.obj.Item;

} // main()

 

 

 

public class Item {

}

 

 

output:

=={{header|JavaScript}}==

Brute force.

panacea = { 'value': 3000, 'weight': 0.3, 'volume': 0.025 },

ichor = { 'value': 1800, 'weight': 0.2, 'volume': 0.015 },

(gold: 11, panacea: 3, ichor: 10)

(gold: 11, panacea: 6, ichor: 5)

 

 

 

 

 

 

=={{header|Lua}}==

["ichor"] = { ["value"] = 1800, ["weight"] = 0.2, ["volume"] = 0.015 },

["gold"] = { ["value"] = 2500, ["weight"] = 2.0, ["volume"] = 0.002 }

for k, v in pairs( best_amounts ) do

print( k, v )

 

Brute force algorithm:

{iva,iwe,ivo}={1800,2/10,3/200};

{gva,gwe,gvo}={2500,2,2/1000};

data=Flatten[Table[{{p,i,g}.{pva,iva,gva},{p,i,g}.{pwe,iwe,gwe},{p,i,g}.{pvo,ivo,gvo},{p,i,g}},{p,0,pmax},{i,0,imax},{g,0,gmax}],2];

data=Select[data,#[[2]]<=25&&#[[3]]<=1/4&];

gives back an array of the best solution(s), with each element being value, weight, volume, {number of vials, number of ampules, number of bars}:

if we call the three items by their first letters the best packings are:

p:6 i:5 v:11

p:3 i:10 v:11

The volume for all of those is the same, the 'best' solution would be the one that has the least weight: that would the first solution.

 

=={{header|Mathprog}}==

This model finds the integer optimal packing of a knapsack

;

 

The solution produced is at [[Knapsack problem/Unbounded/Mathprog]].

 

{{trans|Fortran}}

Note that unlike [[Fortran]] and [[C]], Modula-3 does not do any hidden casting, which is why <tt>FLOAT</tt> and <tt>FLOOR</tt> are used.

 

FROM IO IMPORT Put;

Put("This is achieved by carrying " & Int(n[1]) & " panacea, " & Int(n[2]) & " ichor and " & Int(n[3]) & " gold items\n");

Put("The weight of this carry is " & Real(totalWeight) & " and the volume used is " & Real(totalVolume) & "\n");

Output:

<pre>Maximum value achievable is 54500

This is achieved by carrying 0 panacea, 15 ichor and 11 gold items

The weight of this carry is 25 and the volume used is 0.247</pre>

 

=={{header|OCaml}}==

This is a brute-force solution: it generates a list of every legal combination of items and then finds the best results:

 

let bounty n d w v = { name = n; value = d; weight = w; volume = v }

print_newline()

 

 

outputs:

=={{header|Oz}}==

Using constraint propagation and branch and bound search:

proc {Knapsack Sol}

solution(panacea:P = {FD.decl}

{System.showInfo "\nResult:"}

{Show Best}

 

If you study the output, you see how the weight and volume equations automagically constrain the domain of the three variables.

=={{header|Pascal}}==

With ideas from C, Fortran and Modula-3.

 

uses

writeln ('This is achieved by carrying ', n[1], ' panacea, ', n[2], ' ichor and ', n[3], ' gold items');

writeln ('The weight of this carry is ', totalWeight:6:3, ' and the volume used is ', totalVolume:6:4);

Output:

<pre>:> ./Knapsack

=={{header|Perl}}==

Dynamic programming solution. Before you ask, no, it's actually slower for the given data set. See the alternate data set.

 

if (1) { # change 1 to 0 for different data set

$wtot/$wsc, $vtot/$vsc, $x->[0];

 

 

Output:<pre>Max value 54500, with:

Cache info is not pertinent to this task, just some info.

 

 

 

 

 

 

 

 

=={{header|PicoLisp}}==

Brute force solution

("panacea" 3 25 3000)

("ichor" 2 15 1800)

(inc 'N) )

(apply tab X (4 2 8 5 5 7) N "x") ) )

Output:

<pre> 15 x ichor 2 15 1800

=={{header|PowerShell}}==

{{works with|PowerShell|3.0}}

$Item = @(

[pscustomobject]@{ Name = 'panacea'; Unit = 'vials' ; value = 3000; Weight = 0.3; Volume = 0.025 }

# Show the results

{{out}}

<pre>0 vials of panacea, 15 ampules of ichor, and 11 bars of gold worth a total of 54500.

=={{header|Prolog}}==

Works with SWI-Prolog and <b>library simplex</b> written by <b>Markus Triska</b>.

 

% tuples (name, Explantion, Value, weights, volume).

W2 is W1 + Wtemp,

Vo2 is Vo1 + Votemp ),

Output :

<pre> ?- knapsack.

=={{header|PureBasic}}==

{{trans|Fortran}}

Define.i maxPanacea, maxIchor, maxGold, maxValue

Define.i i, j ,k

Data.i 0

Data.f 25.0, 0.25

 

Outputs

=={{header|R}}==

Brute force method

weights <- c(panacea=0.3, ichor=0.2, gold=2.0)

volumes <- c(panacea=0.025, ichor=0.015, gold=0.002)

# Find the solutions with the highest value

vals <- apply(knapok, 1, getTotalValue)

panacea ichor gold

2067 9 0 11

Using Dynamic Programming

 

Data_<-structure(list(item = c("Panacea", "Ichor", "Gold"), value = c(3000,

1800, 2500), weight = c(3, 2, 20), volume = c(25, 15, 2)), .Names = c("item",

 

main_knapsack(Data_, 250, 250)

Output:

The Total profit is: 54500

You must carry: Gold (x 11 )

You must carry: Panacea (x 9 )

 

=={{header|Racket}}==

 

#lang racket

 

(call-with-values (λ() (fill-sack items 0.25 25 '() 0))

(λ(sacks total) (for ([s sacks]) (display-sack s total))))

 

{{out}}

Take 9 panacea (vials of)

GRAND TOTAL: 54500</pre>

 

=={{header|REXX}}==

{{trans|Fortran}}

===displays 1st solution===

 

maxPanacea= min(sack.w / panacea.w, sack.v / panacea.v)

now.w= g * gold.w + i * ichor.w + p * panacea.w

now.v= g * gold.v + i * ichor.v + p * panacea.v

end

end /*g (gold) */

end /*p (panacea)*/

 

say left('', 40) "total value: " max$ / 1

say left('', 40) "total weight: " maxW / 1

say left('', 40) "total volume: " maxV / 1

<pre>

panacea in sack: 0

 

===displays all solutions===

 

maxPanacea= min(sack.w / panacea.w, sack.v / panacea.v)

maxIchor = min(sack.w / ichor.w, sack.v / ichor.v)

now.w = g * gold.w + i * ichor.w + p * panacea.w

now.v = g * gold.v + i * ichor.v + p * panacea.v

end

end /*g (gold) */

end /*i (ichor) */

end /*p (panacea)*/

end /*j*/

<pre>

▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒ solution 1

=={{header|Ruby}}==

Brute force method, {{trans|Tcl}}

panacea = KnapsackItem.new(0.025, 0.3, 3000)

ichor = KnapsackItem.new(0.015, 0.2, 1800)

i*ichor.weight + p*panacea.weight + g*gold.weight,

i*ichor.volume + p*panacea.volume + g*gold.volume

{{out}}

<pre>

=={{header|SAS}}==

This is yet another brute force solution.

wtpanacea=0.3; wtichor=0.2; wtgold=2.0;

volpanacea=0.025; volichor=0.015; volgold=0.002;

proc print data=one (obs=4);

var panacea ichor gold vals;

Output:

<pre>

</pre>

 

 

 

 

 

 

 

 

 

}

 

<pre>

</pre>

 

=={{header|Seed7}}==

include "float.s7i";

 

writeln("This is achieved by carrying " <& bestAmounts[1] <& " panacea, " <& bestAmounts[2] <& " ichor and " <& bestAmounts[3] <& " gold items");

writeln("The weight of this carry is " <& best.weight <& " and the volume used is " <& best.volume digits 4);

 

Output:

=={{header|Sidef}}==

{{trans|Perl}}

Number volume,

Number weight,

#{"-" * 50}

Total:\t #{"%8d%8g%8d" % (wtot/wsc, vtot/vsc, x[0])}

{{out}}

<pre>

 

=={{header|Tcl}}==

proc main argv {

array set value {panacea 3000 ichor 1800 gold 2500}

puts "maxval: $maxval, best: $best"

}

 

<pre>$ time tclsh85 /Tcl/knapsack.tcl

filter them by the volume and weight restrictions, partition the remaining packings

by value, and search for the maximum value class.

#import flo

 

#cast %nmL

 

output:

<pre><

whilst the one below is focussing more on expressing/solving the problem

in less lines of code.

 

Sub Main()

If M(Value) = S(1)(Value) Then Debug.Print M(Value), M(Weight), M(Volume), M(PC), M(IC), M(GC)

Next

Output:<pre> Value Weight Volume PanaceaCount IchorCount GoldCount

54500 24.7 0.247 9 0 11

54500 24.9 0.247 3 10 11

54500 25 0.247 0 15 11

</pre>

 

=={{header|zkl}}==

{{trans|D}}

ichor :=T(1800, 0.2, 0.015);

gold :=T(2500, 2.0, 0.002);

" %d panacea, %d ichor and %d gold").fmt(best[1].xplode()));

println("The weight to carry is %4.1f and the volume used is %5.3f"

cprod3 is the Cartesian product of three lists or iterators.

{{out}}