79 lines
2.3 KiB
Text
79 lines
2.3 KiB
Text
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)
|