Knapsack problem/Unbounded: Difference between revisions

{{trans|Python}}

Int value

Float weight, volume

print(‘Maximum value achievable is ’best.value)

print(‘This is achieved by carrying (one solution) #. panacea, #. ichor and #. gold’.format(best_amounts[0], best_amounts[1], best_amounts[2]))

{{out}}

{{trans|Visual Basic}}

The program uses two ASSIST macros (XDECO,XPRNT) to keep the code as short as possible.

KNAPSACK CSECT

USING KNAPSACK,R13 base register

PG DS CL72

YREGS

{{out}}

<pre>

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

=={{header|C sharp|C#}}==

a 30 3 25

b 18 2 15

return new uint[] { a0, b0, c0 };

}

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

This model finds the integer optimal packing of a knapsack

}

}

Produces:

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

=={{header|Elixir}}==

Brute Force:

defstruct volume: 0.0, weight: 0.0, value: 0

def new(volume, weight, value) do

gold: Item.new(0.002, 2.0, 2500) }

maximum = Item.new(0.25, 25, 0)

{{out}}

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

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

'''Works with gojq, the Go implementation of jq'''

{$name, $value, $weight, $volume};

f(.itemCount; .sumNumber; .bestValue; .sumWeight; .sumVolume) );

{{out}}

<pre>

=={{header|Julia}}==

using JuMP

using GLPKMathProgInterface

println("vials of panacea = ", getvalue(vials_of_panacea))

println("ampules of ichor = ", getvalue(ampules_of_ichor))

{{output}}

<pre>

{{trans|C}}

Recursive brute force approach:

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

print("${itemCount} items ${"%2d".format(sumNumber)} ${"%5.0f".format(bestValue)} ${"%4.1f".format(sumWeight)}")

println(" ${"%4.2f".format(sumVolume)}")

{{out}}

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

=={{header|MiniZinc}}==

%Knapsack problem/Unbounded. Nigel Galloway, August 13th., 2021

enum Items ={panacea,ichor,gold};

solve maximize sum(n in Items)(value[n]*take[n]);

output(["Take "++show(take[panacea])++" vials of panacea\nTake "++show(take[ichor])++" ampules of ichor\nTake "++ show(take[gold])++" bars of gold\n"])

{{out}}

<pre>

=={{header|M4}}==

A brute force solution:

define(`set2d',`define(`$1[$2][$3]',`$4')')

define(`get2d',`defn(`$1[$2][$3]')')

')')

divert

Output:

<pre>54500 (0,15,11) (3,10,11) (6,5,11) (9,0,11)</pre>

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

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

{{trans|Pascal}}

This is a brute-force solution translated from Pascal to Nim, which is straightforward.

import lenientops # Mixed float/int operators.

echo fmt"Maximum value achievable is {maxValue}."

echo fmt"This is achieved by carrying {n[1]} panacea, {n[2]} ichor and {n[3]} gold items."

{{out}}

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

For each goodie, fill yer boots, then (except for the last) recursively try with fewer and fewer.<br>

Increase profit and decrease weight/volume to pick largest profit for least weight and space.

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

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

<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Profit %d: %s [weight:%.1f, volume:%g]\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">profit</span><span style="color: #0000FF;">,</span><span style="color: #000000;">what</span><span style="color: #0000FF;">,</span><span style="color: #000000;">weight</span><span style="color: #0000FF;">,</span><span style="color: #000000;">volume</span><span style="color: #0000FF;">})</span>

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

{{out}}

<pre>

=={{header|Picat}}==

This is a typical constraint modelling problem. We must use the MIP solver - using the mip module - for this problem since the data contains float values (which neither of the CP/SAT/SMT solvers support).

go =>

Volume = [ 0.025, 0.015, 0.002],

MaxWeight = 25.0,

{{out}}

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

Brute force, looked a lot at the Ruby solution.

has $.volume;

has $.weight;

say "maximum value is $max_val\npossible solutions:";

say "panacea\tichor\tgold";

'''Output:'''

<pre>maximum value is 54500

{{trans|Fortran}}

===displays 1st solution===

/* value weight volume */

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

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

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

<pre>

===displays all solutions===

maxPanacea= 0

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

end /*j*/

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

<pre>

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

Use SAS/OR:

data mydata;

input Item $1-19 Value weight Volume;

print TotalValue;

for {s in 1.._NSOL_} print {i in ITEMS} NumSelected[i].sol[s];

MILP solver output:

=={{header|Scala}}==

===Functional approach (Tail recursive)===

object UnboundedKnapsack extends App {

packer(items.map(i => Knapsack(Seq(i))), Nil).foreach(println)

{{out}}

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

The following code uses brute force, but that's tolerable as long as it takes just a split second to find all 4 solutions. The use of arrays makes the code quite legible:

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

{{trans|Kotlin}}

{{libheader|Wren-fmt}}

class Item {

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

Fmt.write("$d items $2d $5.0f $4.1f", itemCount, sumNumber, bestValue, sumWeight)

{{out}}

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