58 lines
1.9 KiB
D
58 lines
1.9 KiB
D
import std.stdio, std.typecons, std.functional;
|
|
|
|
immutable struct Item {
|
|
string name;
|
|
int weight, value, quantity;
|
|
}
|
|
|
|
immutable Item[] items = [
|
|
{"map", 9, 150, 1}, {"compass", 13, 35, 1},
|
|
{"water", 153, 200, 3}, {"sandwich", 50, 60, 2},
|
|
{"glucose", 15, 60, 2}, {"tin", 68, 45, 3},
|
|
{"banana", 27, 60, 3}, {"apple", 39, 40, 3},
|
|
{"cheese", 23, 30, 1}, {"beer", 52, 10, 3},
|
|
{"suntan cream", 11, 70, 1}, {"camera", 32, 30, 1},
|
|
{"t-shirt", 24, 15, 2}, {"trousers", 48, 10, 2},
|
|
{"umbrella", 73, 40, 1}, {"w-trousers", 42, 70, 1},
|
|
{"w-overcoat", 43, 75, 1}, {"note-case", 22, 80, 1},
|
|
{"sunglasses", 7, 20, 1}, {"towel", 18, 12, 2},
|
|
{"socks", 4, 50, 1}, {"book", 30, 10, 2}];
|
|
|
|
Tuple!(int, const(int)[]) chooseItem(in int iWeight, in int idx) nothrow @safe {
|
|
alias memoChooseItem = memoize!chooseItem;
|
|
if (idx < 0)
|
|
return typeof(return)();
|
|
|
|
int bestV;
|
|
const(int)[] bestList;
|
|
with (items[idx])
|
|
foreach (immutable i; 0 .. quantity + 1) {
|
|
immutable wlim = iWeight - i * weight;
|
|
if (wlim < 0)
|
|
break;
|
|
|
|
//const (val, taken) = memoChooseItem(wlim, idx - 1);
|
|
const val_taken = memoChooseItem(wlim, idx - 1);
|
|
if (val_taken[0] + i * value > bestV) {
|
|
bestV = val_taken[0] + i * value;
|
|
bestList = val_taken[1] ~ i;
|
|
}
|
|
}
|
|
|
|
return tuple(bestV, bestList);
|
|
}
|
|
|
|
void main() {
|
|
// const (v, lst) = chooseItem(400, items.length - 1);
|
|
const v_lst = chooseItem(400, items.length - 1);
|
|
|
|
int w;
|
|
foreach (immutable i, const cnt; v_lst[1])
|
|
if (cnt > 0) {
|
|
writeln(cnt, " ", items[i].name);
|
|
w += items[i].weight * cnt;
|
|
}
|
|
|
|
writeln("Total weight: ", w, " Value: ", v_lst[0]);
|
|
}
|