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

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

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

 

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

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.

Value = 3000,1800,2500

Weight= 3,2,20 ; *10

}

}

=={{header|Bracmat}}==

( things

= (panacea.3000.3/10.25/1000)

 

!knapsack;

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.

#include <stdlib.h>

 

return 0;

}

{{output}}<pre>9 panacea

0 ichor

11 gold

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

This model finds the integer optimal packing of a knapsack

}

}

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

 

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

Total weight: 24.7

Total volume: 0.247

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)

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.

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

250 ; total volume

247) ; total weight</pre>

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

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.

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)

 

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

=={{header|Eiffel}}==

class

KNAPSACK

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:

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

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

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

 

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

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)

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

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)

}

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.

import Data.Ord (comparing)

 

 

main = putStr $ showOpt $ best options

ichor: 0

gold: 11

total volume: 0.247

total value: 54500</pre>

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

panacea: 3

ichor: 10

total volume: 0.247

total value: 54500</pre>

=={{header|Java}}==

With recursion for more than 3 items.

 

import hu.pj.obj.Item;

} // main()

 

 

 

public class Item {

}

 

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.

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

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

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

using JuMP

using GLPKMathProgInterface

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

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

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

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

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

 

{{out}}

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

panacea 9 27000 2.7 0.23

gold 11 27500 22.0 0.02

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

 

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

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

{{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");

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

 

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:

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.

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.

 

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

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.

 

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

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

 

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

11 x gold 20 2 2500

250 247 54500</pre>

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

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

 

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

W2 is W1 + Wtemp,

Vo2 is Vo1 + Votemp ),

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

Define.i maxPanacea, maxIchor, maxGold, maxValue

Define.i i, j ,k

Data.i 0

Data.f 25.0, 0.25

 

Outputs

Press Enter to quit</tt>

=={{header|Python}}==

See [[Knapsack Problem/Python]]

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

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

}

 

Output:

The Total profit is: 54500

You must carry: Gold (x 11 )

You must carry: Panacea (x 9 )

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

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

ichors in sack: 15

gold items in sack: 11

total value: 54500

total weight: 25

===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*/

panacea in sack: 0

ichors in sack: 15

total value: 54500

total weight: 24.7

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

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.

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;

 

1 0 15 11 54500

2 3 10 11 54500

3 6 5 11 54500

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

54500

 

gold (bars) 11

ichor (ampules of) 0

54500

 

ichor (ampules of) 0

panacea (vials of) 9 </pre>

=={{header|Scala}}==

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

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)

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

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

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

=={{header|Sidef}}==

{{trans|Perl}}

Number volume,

Number weight,

#{"-" * 50}

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

{{out}}

Item Qty Weight Vol Value

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

gold: 11 22 0.022 27500

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

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

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,

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

 

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

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.8 0.247 6 5 11

54500 24.9 0.247 3 10 11

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

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

[[Category:Puzzles]]