Knapsack problem/Unbounded: Difference between revisions
→{{header|jq}}
m (→{{header|Tcl}}: code) |
|||
Line 2,061:
(gold: 11, panacea: 6, ichor: 5)
(gold: 11, panacea: 9, ichor: 0)</pre></lang>
=={{header|jq}}==
{{trans|Wren}}
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
<lang jq>def Item($name; $value; $weight; $volume):
{$name, $value, $weight, $volume};
def items:[
Item("panacea"; 3000; 0.3; 0.025),
Item("ichor"; 1800; 0.2; 0.015),
Item("gold"; 2500; 2; 0.002)
];
def array($init): [range(0; .) | $init];
# input: {count, best, bestvalue}
def knapsack($i; $value; $weight; $volume):
(items|length) as $n
| if $i == $n
then if $value > .bestValue
then .bestValue = $value
| reduce range(0; $n) as $j (.; .best[$j] = .count[$j])
else .
end
else (($weight / items[$i].weight)|floor) as $m1
| (($volume / items[$i].volume)|floor) as $m2
| .count[$i] = ([$m1, $m2] | min)
| until (.count[$i] < 0;
knapsack(
$i + 1;
$value + .count[$i] * (items[$i].value);
$weight - .count[$i] * (items[$i].weight);
$volume - .count[$i] * (items[$i].volume)
)
| .count[$i] += -1
)
end ;
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
def solve($maxWeight; $maxVolume):
def rnd: 100 * . | round / 100;
def rnd($width): if type == "string" then lpad($width) else rnd|lpad($width) end;
def f(a;b;c;d;f):
"\(a|lpad(11)) \(b|rnd(6)) \(c|rnd(6)) \(d|rnd(6)) \(f|rnd(6))" ;
def f: . as [$a,$b,$c,$d,$f] | f($a;$b;$c;$d;$f);
(items|length) as $n
| def init:
{ count: ($n|array(0)),
best : ($n|array(0)),
bestValue: 0,
maxWeight: $maxWeight,
maxVolume: $maxVolume };
f("Item Chosen"; "Number"; "Value"; "Weight"; "Volume"),
"----------- ------ ------ ------ ------",
( init
| knapsack(0; 0; $maxWeight; $maxVolume)
| reduce range(0; $n) as $i (
. + {itemCount:0, sumNumber:0, sumWeight:0, sumVolume:0 };
if (.best[$i]) != 0
then .itemCount += 1
| .name = items[$i].name
| .number = .best[$i]
| .value = items[$i].value * .number
| .weight = items[$i].weight * .number
| .volume = items[$i].volume * .number
| .sumNumber += .number
| .sumWeight += .weight
| .sumVolume += .volume
| .emit += [ f(.name; .number; .value; .weight; .volume) ]
else .
end)
| .emit[],
"----------- ------ ------ ------ ------",
f(.itemCount; .sumNumber; .bestValue; .sumWeight; .sumVolume) );
solve(25; 0.25)</lang>
{{out}}
<pre>
Item Chosen Number Value Weight Volume
----------- ------ ------ ------ ------
panacea 9 27000 2.7 0.23
gold 11 27500 22 0.02
----------- ------ ------ ------ ------
2 20 54500 24.7 0.25
</pre>
=={{header|Julia}}==
| |||