Knapsack problem/Bounded: Difference between revisions

}</lang>

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

Similar to Knapsack/0-1.

<lang csharp>using System; // 4790@3.6

class program

{

static void Main()

{

knapSack(40);

var sw = System.Diagnostics.Stopwatch.StartNew();

Console.Write(knapSack(400) + "\n" + sw.Elapsed); // 51 µs

Console.Read();

}

static string knapSack(uint w1)

{

init(); change();

uint n = (uint)w.Length; var K = new uint[n + 1, w1 + 1];

for (uint vi, wi, w0, x, i = 0; i < n; i++)

for (vi = v[i], wi = w[i], w0 = 1; w0 <= w1; w0++)

{

x = K[i, w0];

if (wi <= w0) x = max(vi + K[i, w0 - wi], x);

K[i + 1, w0] = x;

}

string str = "";

for (uint v1 = K[n, w1]; v1 > 0; n--)

if (v1 != K[n - 1, w1])

{

v1 -= v[n - 1]; w1 -= w[n - 1]; str += items[n - 1] + "\n";

}

return str;

}

static uint max(uint a, uint b) { return a > b ? a : b; }

static byte[] w, v; static string[] items;

static byte[] p = { 1, 1, 2, 2, 2, 3, 3, 3, 1, 3, 1, 1, 2, 2, 1, 1, 1, 1, 1, 2, 1, 2 };

static void init()

{

w = new byte[] { 9, 13, 153, 50, 15, 68, 27, 39, 23, 52, 11,

32, 24, 48, 73, 42, 43, 22, 7, 18, 4, 30 };

v = new byte[] { 150, 35, 200, 60, 60, 45, 60, 40, 30, 10, 70,

30, 15, 10, 40, 70, 75, 80, 20, 12, 50, 10 };

items = new string[] {"map","compass","water","sandwich","glucose","tin",

"banana","apple","cheese","beer","suntan cream",

"camera","T-shirt","trousers","umbrella",

"waterproof trousers","waterproof overclothes",

"note-case","sunglasses","towel","socks","book"};

}

static void change()

{

int n = w.Length, s = 0, i, j, k; byte xi;

for (i = 0; i < n; i++) s += p[i];

{

byte[] x = new byte[s];

for (k = i = 0; i < n; i++)

for (xi = w[i], j = p[i]; j > 0; j--) x[k++] = xi;

w = x;

}

{

byte[] x = new byte[s];

for (k = i = 0; i < n; i++)

for (xi = v[i], j = p[i]; j > 0; j--) x[k++] = xi;

v = x;

}

string[] pItems = new string[s]; string itemI;

for (k = i = 0; i < n; i++)

for (itemI = items[i], j = p[i]; j > 0; j--) pItems[k++] = itemI;

items = pItems;

}

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

==== Original ====

Recursive algorithm, with cache. Idiomatic code style, using multi-subs and a class.

{{works with|Rakudo|2017.01}}

<lang perl6>my class KnapsackItem { has $.name; has $.weight; has $.unit; }

multi sub pokem ([], $, $v = 0) { $v }

multi sub pokem ([$, *@], 0, $v = 0) { $v }

multi sub pokem ([$i, *@rest], $w, $v = 0) {

my $key = "{+@rest} $w $v";

(state %cache){$key} or do {

my @skip = pokem @rest, $w, $v;

if $w >= $i.weight { # next one fits

my @put = pokem @rest, $w - $i.weight, $v + $i.unit;

return (%cache{$key} = |@put, $i.name).list if @put[0] > @skip[0];

}

return (%cache{$key} = |@skip).list;

}

}

my $MAX_WEIGHT = 400;

my @table = flat map -> $name, $weight, $unit, $count {

KnapsackItem.new( :$name, :$weight, :$unit ) xx $count;

},

'map', 9, 150, 1,

'compass', 13, 35, 1,

'water', 153, 200, 2,

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

'waterproof trousers', 42, 70, 1,

'waterproof overclothes', 43, 75, 1,

'note-case', 22, 80, 1,

'sunglasses', 7, 20, 1,

'towel', 18, 12, 2,

'socks', 4, 50, 1,

'book', 30, 10, 2

;

my ($value, @result) = pokem @table, $MAX_WEIGHT;

(my %hash){$_}++ for @result;

say "Value = $value";

say "Tourist put in the bag:";

say " # ITEM";

for %hash.sort -> $item {

say " {$item.value} {$item.key}";

}</lang>

{{out}}

<pre>Value = 1010

Tourist put in the bag:

# ITEM

3 banana

1 cheese

1 compass

2 glucose

1 map

1 note-case

1 socks

1 sunglasses

1 suntan cream

1 water

1 waterproof overclothes</pre>

==== Faster alternative ====

Also recursive, with cache, but substantially faster. Code more generic (ported from Perl solution).

<lang perl6>my $raw = qq:to/TABLE/;

map 9 150 1

compass 13 35 1

water 153 200 2

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 1

suntancream 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

TABLE

my @items;

for split(["\n", /\s+/], $raw, :skip-empty) -> $n,$w,$v,$q {

@items.push: %{ name => $n, weight => $w, value => $v, quant => $q}

}

my $max_weight = 400;

sub pick ($weight, $pos) {

state %cache;

return 0, 0 if $pos < 0 or $weight <= 0;

my $key = $weight ~ $pos;

%cache{$key} or do {

my %item = @items[$pos];

my ($bv, $bi, $bw, @bp) = (0, 0, 0);

for 0 .. %item{'quant'} -> $i {

last if $i * %item{'weight'} > $weight;

my ($v, $w, @p) = pick($weight - $i * %item{'weight'}, $pos - 1);

next if ($v += $i * %item{'value'}) <= $bv;

($bv, $bi, $bw, @bp) = ($v, $i, $w, |@p);

}

%cache{$key} = $bv, $bw + $bi * %item{'weight'}, |@bp, $bi;

}

}

my ($v, $w, @p) = pick($max_weight, @items.end);

{ say "{@p[$_]} of @items[$_]{'name'}" if @p[$_] } for 0 .. @p.end;

say "Value: $v Weight: $w";</lang>

{{out}}

<pre>1 of map

1 of compass

1 of water

2 of glucose

3 of banana

1 of cheese

1 of suntancream

1 of w_overcoat

1 of note-case

1 of sunglasses

1 of socks

Value: 1010 Weight: 396</pre>