Knapsack problem/Unbounded: Difference between revisions

{{task|Classic CS problems and programs}}

 

 

 

 

<br>

;Task:

;Note:

<!-- All solutions

# ((value, -weight, -volume), (#panacea, #ichor, #gold)

[((54500, -25.0, -0.24699999999999997), (0, 15, 11)),

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

-->

;Related tasks:

=={{header|360 Assembly}}==

{{trans|Visual Basic}}

END KNAPSACK</lang>

{{out}}

54500 24.7 0.247 9 0 11

54500 24.8 0.247 6 5 11

54500 25.0 0.247 0 15 11

</pre>

=={{header|Ada}}==

{{trans|Python}}

<lang Ada>with Ada.Text_IO;

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

end Knapsack_Unbounded;</lang>

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

{{trans|Python}}<lang algol68>MODE BOUNTY = STRUCT(STRING name, INT value, weight, volume);

name OF items, max items));

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

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

The weight to carry is 247, and the volume used is 247</pre>

=={{header|AutoHotkey}}==

Brute Force.

<lang AutoHotkey>Item = Panacea,Ichor,Gold

}

MsgBox Value = %$%`n`nPanacea`tIchor`tGold`tWeight`tVolume`n%t%</lang>

=={{header|Bracmat}}==

<lang bracmat>(knapsack=

!knapsack;

</lang>

Finally take 11 items of gold.

The value in the knapsack is 54500.</pre>

=={{header|C}}==

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

<lang c>#include <stdio.h>

#include <stdlib.h>

}

</lang>

{{output}}<pre>9 panacea

0 ichor

11 gold

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

<lang csharp>/*Knapsack

}

}</lang>

Date: 28/01/2012 17:18:56

Version: Microsoft Solver Foundation 3.0.1.10599 Express Edition

take(Panacea): 9

take(Ichor): 0

=={{header|Clojure}}==

<lang lisp>(defstruct item :value :weight :volume)

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

(println "Containing: " p "Panacea," i "Ichor," g "Gold")))</lang>

Total weight: 24.7

Total volume: 0.247

(print-knapsack k)

(println)))</lang>

Total weight: 25.0

Total volume: 0.247

Total weight: 24.7

Total volume: 0.247

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

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

250 ; total volume

247) ; total weight</pre>

=={{header|D}}==

{{trans|Python}}

This is achieved by carrying (one solution) 0 panacea, 15 ichor and 11 gold

The weight to carry is 25.0 and the volume used is 0.247</pre>

===Alternative Version===

The output is the same.

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

}</lang>

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

<lang e>pragma.enable("accumulator")

 

printBest(emptyKnapsack, [panacea, ichor, gold])</lang>

=={{header|EchoLisp}}==

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

 

(length (hash-keys H)) ;; # entries in cache

=={{header|Eiffel}}==

<lang Eiffel>

end

 

{{out}}

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

The weight is 25 and the volume is 0.247.

</pre>

=={{header|Elixir}}==

Brute Force:

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

Knapsack.solve_unbounded(items, maximum)</lang>

{{out}}

[gold: 11, ichor: 0, panacea: 9] => 0.247, 24.7, 54500

[gold: 11, ichor: 5, panacea: 6] => 0.247, 24.8, 54500

[gold: 11, ichor: 15, panacea: 0] => 0.247, 25.0, 54500

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

<lang factor>USING: accessors combinators kernel locals math math.order

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

[ <bounty> ] [ max ] map-reduce ;</lang>

=={{header|Forth}}==

<lang forth>\ : value ; immediate

The traveller's knapsack contains 0 vials of panacea, 15 ampules of ichor,

11 bars of gold, a total value of 54500. ok

=={{header|Fortran}}==

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

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.

sumCount, sumWeight, sumVolume, sumValue)

}</lang>

Ichor x 0 -> Weight: 0.0 Volume: 0.000 Value: 0

Gold x 11 -> Weight: 22.0 Volume: 0.022 Value: 27500

TOTAL ( 20 items) Weight: 24.7 Volume: 0.247 Value: 54500

</pre>

=={{header|Groovy}}==

Solution: dynamic programming

}

}</lang>

Elapsed Time: 26.883 s

 

item: gold (bars) count:11 weight:22.0 Volume:0.022

item: panacea (vials of) count: 9 weight: 2.7 Volume:0.225</pre>

Total Volume: 0.247

Total Value: 54500

item: ichor (ampules of) count: 5 weight: 1.0 Volume:0.075

item: panacea (vials of) count: 6 weight: 1.8 Volume:0.150</pre>

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

main = putStr $ showOpt $ best options

where best = maximumBy $ comparing $ dotProduct vals</lang>

ichor: 0

gold: 11

total volume: 0.247

total value: 54500</pre>

=={{header|HicEst}}==

<lang hicest>CHARACTER list*1000

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

value=54500; Panaceas=9; Ichors=0; Golds=11; weight=24.7; volume=0.247; </lang>

=={{header|J}}==

Brute force solution.

LF

)</lang>

panacea: 3

ichor: 10

total volume: 0.247

total value: 54500</pre>

=={{header|Java}}==

With recursion for more than 3 items.

 

} // class</lang>

This is achieved by carrying (one solution): 0 panacea, 15 ichor, 11 gold,

The weight to carry is: 25 and the volume used is: 0,247</pre>

=={{header|JavaScript}}==

Brute force.

item = solutions[i];

document.write("(gold: " + item[0] + ", panacea: " + item[1] + ", ichor: " + item[2] + ")<br>");

(gold: 11, panacea: 0, ichor: 15)

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

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

=={{header|Julia}}==

{{libheader|JuMP}}<lang julia>

println("bars of gold = ", getvalue(bars_of_gold))</lang>

{{output}}

Max 3000 vials_of_panacea + 1800 ampules_of_ichor + 2500 bars_of_gold

Subject to

vials of panacea = 9.0

ampules of ichor = 0.0

=={{header|Kotlin}}==

{{trans|C}}

Recursive brute force approach:

 

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

 

{{out}}

----------- ------ ----- ------ ------

panacea 9 27000 2.7 0.23

gold 11 27500 22.0 0.02

----------- ------ ----- ------ ------

=={{header|M4}}==

A brute force solution:

divert

mv best</lang>

=={{header|Lua}}==

<lang lua>items = { ["panaea"] = { ["value"] = 3000, ["weight"] = 0.3, ["volume"] = 0.025 },

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

print( k, v )

end</lang>

=={{header|Mathematica}}==

Brute force algorithm:

p:0 i:15 v:11</lang>

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

<lang mathprog>/*Knapsack

end;</lang>

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

=={{header|Modula-3}}==

{{trans|Fortran}}

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

END Knapsack.</lang>

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 () = List.iter print best_results</lang>

Total weight: 24.7

Total volume: 0.247

Total volume: 0.247

Containing: 0 panacea, 15 ichor, 11 gold</pre>

=={{header|OOCalc}}==

OpenOffice.org Calc has (several) linear solvers. To solve this task, first copy in the table from the task description, then add the extra columns:

to produce in seconds:

:[[File:Unbounded Knapsack problem result.PNG|center|Table solved]]

=={{header|Oz}}==

Using constraint propagation and branch and bound search:

 

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

0#solution(gold:_{0#134217726} ichor:_{0#134217726} panacea:_{0#134217726})

1#solution(gold:_{0#12} ichor:_{0#125} panacea:_{0#83})

Result:

solution(gold:11 ichor:15 panacea:0)

=={{header|Pascal}}==

With ideas from C, Fortran and Modula-3.

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

end.</lang>

Maximum value achievable is 54500

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

=={{header|Perl}}==

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

 

print "\nCache hit: $hits\tmiss: $misses\n";</lang>

Output:<pre>Max value 54500, with:

Item Qty Weight Vol Value

Cache hit: 0 miss: 218</pre>

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

=={{header|Perl 6}}==

{{Works with|rakudo|2016.08}}

say "panacea\tichor\tgold";

.join("\t").say for @solutions;</lang>

possible solutions:

panacea ichor gold

6 5 11

9 0 11</pre>

=={{header|Phix}}==

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

printf(1," [weight:%g, volume:%g, %d attempts]\n",

{weight,volume,attempts})</lang>

You get the same result whatever order the goodies are in, but with a different number of attempts, gold/ichor/panacea being the

highest at 204.

=={{header|PicoLisp}}==

Brute force solution

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

(tab (14 5 5 7) NIL (sum cadr K) (sum caddr K) (sum cadddr K)) )</lang>

11 x gold 20 2 2500

250 247 54500</pre>

=={{header|PowerShell}}==

{{works with|PowerShell|3.0}}

6 vials of panacea, 5 ampules of ichor, and 11 bars of gold worth a total of 54500.

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

=={{header|Prolog}}==

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

Vo2 is Vo1 + Votemp ),

print_results(S, A0, A1, A2, A3, A4, T, TN, Va2, W2, Vo2).</lang>

% 145,319 inferences, 0.078 CPU in 0.079 seconds (99% CPU, 1860083 Lips)

Nb Items Value Weigth Volume

54500 25.00 0.247

true </pre>

=={{header|PureBasic}}==

{{trans|Fortran}}

Press Enter to quit</tt>

=={{header|Python}}==

See [[Knapsack Problem/Python]]

=={{header|R}}==

Brute force method

2171 3 10 11

2223 0 15 11

 

Using Dynamic Programming

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

"value", "weight", "volume"), row.names = c(NA, 3L), class = "data.frame")

}

 

<lang r>

Output:

You must carry: Panacea (x 9 )

</lang>

=={{header|Racket}}==

 

(struct item (name explanation value weight volume) #:prefab)

 

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

{{out}}

<pre>Take 11 gold (bars)

Take 9 panacea (vials of)

GRAND TOTAL: 54500</pre>

=={{header|REXX}}==

{{trans|Fortran}}

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

/*stick a fork in it, we're all done. */</lang>

ichors in sack: 15

gold items in sack: 11

total value: 54500

total weight: 25

===displays all solutions===

<lang rexx>/*REXX program solves the knapsack/unbounded problem: highest value, weight, and volume.*/

end /*j*/

/*stick a fork in it, we're all done. */</lang>

panacea in sack: 0

ichors in sack: 15

total value: 54500

total weight: 24.7

=={{header|Ruby}}==

Brute force method, {{trans|Tcl}}

end</lang>

{{out}}

ichor= 0, panacea= 9, gold=11 -- weight:24.7, volume=0.247

ichor= 5, panacea= 6, gold=11 -- weight:24.8, volume=0.247

ichor=10, panacea= 3, gold=11 -- weight:24.9, volume=0.247

ichor=15, panacea= 0, gold=11 -- weight:25.0, volume=0.247</pre>

=={{header|SAS}}==

This is yet another brute force solution.

var panacea ichor gold vals;

run;</lang>

 

1 0 15 11 54500

2 3 10 11 54500

3 6 5 11 54500

Use SAS/OR:

<lang sas>/* create SAS data set */

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

quit;</lang>

54500

 

gold (bars) 11

ichor (ampules of) 0

54500

 

gold (bars) 11

ichor (ampules of) 0

=={{header|Scala}}==

 

object UnboundedKnapsack extends App {

private val (maxWeight, maxVolume) = (BigDecimal(25.0), BigDecimal(0.25))

private val items = Seq(Item("panacea", 3000, 0.3, 0.025), Item("ichor", 1800, 0.2, 0.015), Item("gold", 2500, 2.0, 0.002))

@tailrec

private def packer(notPacked: Seq[Knapsack], packed: Seq[Knapsack]): Seq[Knapsack] = {

def fill(knapsack: Knapsack): Seq[Knapsack] = items.map(i => Knapsack(i +: knapsack.bagged))

def stuffer(Seq: Seq[Knapsack]): Seq[Knapsack] = // Cause brute force

Seq.map(k => Knapsack(k.bagged.sortBy(_.name))).distinct

if (notPacked.isEmpty) packed.sortBy(-_.totValue).take(4)

else packer(stuffer(notPacked.flatMap(fill)).filter(_.isNotFull), notPacked ++ packed)

}

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

private case class Knapsack(bagged: Seq[Item]) {

def isNotFull: Boolean = totWeight <= maxWeight && totVolume <= maxVolume

override def toString = s"[${show(bagged)} | value: $totValue, weight: $totWeight, volume: $totVolume]"

def totValue: Int = bagged.map(_.value).sum

private def totVolume = bagged.map(_.volume).sum

private def totWeight = bagged.map(_.weight).sum

private def show(is: Seq[Item]) =

(items.map(_.name) zip items.map(i => is.count(_ == i)))

.mkString(", ")

}

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

}</lang>

[panacea: 3, ichor: 10, gold: 11 | value: 54500, weight: 24.9, volume: 0.247]

[panacea: 6, ichor: 5, gold: 11 | value: 54500, weight: 24.8, volume: 0.247]

=={{header|Seed7}}==

<lang seed7>$ include "seed7_05.s7i";

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

end func;</lang>

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

=={{header|Sidef}}==

{{trans|Perl}}

EOT</lang>

{{out}}

Item Qty Weight Vol Value

--------------------------------------------------

gold: 11 22 0.022 27500

--------------------------------------------------

=={{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 quote quite legible:

}

main $argv</lang>

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

maxval: 54500, best: {i 0 p 9 g 11} {i 5 p 6 g 11} {i 10 p 3 g 11} {i 15 p 0 g 11}

user 0m0.015s

sys 0m0.015s</pre>

=={{header|Ursala}}==

The algorithm is to enumerate all packings with up to the maximum of each item,

 

human_readable = ~&p/*<'panacea','ichor','gold'> solutions</lang>

<'panacea': 0,'ichor': 15,'gold': 11>,

<'panacea': 3,'ichor': 10,'gold': 11>,

<'panacea': 6,'ichor': 5,'gold': 11>,

<'panacea': 9,'ichor': 0,'gold': 11>></pre>

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

See: [[Knapsack Problem/Visual Basic]]

54500 24.8 0.247 6 5 11

54500 24.9 0.247 3 10 11

=={{header|zkl}}==

{{trans|D}}

cprod3 is the Cartesian product of three lists or iterators.

{{out}}

This is achieved by carrying (one solution): 9 panacea, 0 ichor and 11 gold

[[Category:Puzzles]]