Knapsack problem/Bounded: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|Picat}}: Adding {{out}}) |
m (→{{header|Wren}}: Minor tidy) |
||
| (3 intermediate revisions by 3 users not shown) | |||
Line 82:
{{trans|Python}}
<
‘sandwich’ = (50, 60, 2),
‘map’ = (9, 150, 1),
Line 142:
w += items[name][0] * cnt
print(‘Total weight: ’w‘ Value: ’v)</
{{out}}
Line 162:
=={{header|AutoHotkey}}==
iterative dynamic programming solution
<
,camera,tshirt,trousers,umbrella,waterproof trousers,waterproof overclothes,notecase
,sunglasses,towel,socks,book
Line 198:
}
MsgBox % "Value = " m%N%_%W% "`nWeight = " s "`n`n" t</
=={{header|Bracmat}}==
<
( things
= (map.9.150.1)
Line 274:
);
!knapsack;</
{{out}}
<pre> 1010
Line 291:
=={{header|C}}==
<
#include <stdlib.h>
Line 375:
return 0;
}
</syntaxhighlight>
{{output}}
Line 393:
=={{header|C sharp|C#}}==
Similar to Knapsack/0-1.
<
class program
{
Line 466:
items = pItems;
}
}</
=={{header|C++}}==
C++ DP solution. Initially taken from C but than fixed and refactored.<br>
Remark: The above comment implies there is a bug in the C code, but refers to a much older and very different version [[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 19:28, 20 March 2017 (UTC)
<
#include <vector>
#include <algorithm>
Line 706:
cout << "Weight: " << solution.w << " Value: " << solution.v << endl;
return 0;
}</
=={{header|Clojure}}==
We convert the problem to a Knapsack-0/1 problem by replacing (n-max item) vith n-max identical occurences of 1 item.
Adapted Knapsack-0/1 problem solution from [https://www.rosettacode.org/wiki/Knapsack_problem/0-1#Clojure]
<
(:gen-class))
Line 771:
(println "Total value:" value)
(println "Total weight:" (reduce + (map (comp :weight items) indexes))))
</syntaxhighlight>
{{Output}}
<pre>
Line 791:
=={{header|Common Lisp}}==
<
(defmacro mm-set (p v) `(if ,p ,p (setf ,p ,v)))
Line 824:
(T-shirt 24 15 2) (trousers 48 10 2) (umbrella 73 40 1)
(trousers 42 70 1) (overclothes 43 75 1) (notecase 22 80 1)
(glasses 7 20 1) (towel 18 12 2) (socks 4 50 1) (book 30 10 2))))</
=={{header|Crystal}}==
==== Branch and Bound solution ====
<
record Selection, mask : Array(Int32), cur_index : Int32, total_value : Int32
Line 904:
puts "total weight #{used.sum { |item, count| item.weight*count }}"
puts "total value #{used.sum { |item, count| item.value*count }}"
puts "checked nodes: #{solver.checked_nodes}"</
{{out}}
<pre>optimal choice: map, socks, suntan cream, 2x glucose, note-case, sunglasses, compass, 3x banana, waterproof overclothes, water, cheese
Line 914:
==== Dynamic programming solution ====
{{trans|Ruby}}
<
record Item, name : String, weight : Int32, value : Int32, count : Int32
Line 973:
end
p "Total weight: #{w}, Value: #{val}"</
=={{header|D}}==
{{trans|Python}}
Solution with memoization.
<
immutable struct Item {
Line 1,034:
writeln("Total weight: ", w, " Value: ", v_lst[0]);
}</
{{out}}
<pre>1 map
Line 1,051:
=={{header|EchoLisp}}==
We convert the problem to a Knapsack-0/1 problem by replacing (n-max item) vith n-max identical occurences of 1 item.
<
(lib 'struct)
(lib 'sql)
Line 1,107:
(name i))))
</syntaxhighlight>
{{out}}
<
(define goodies
'((map 9 150 1) (compass 13 35 1)(water 153 200 3)
Line 1,129:
(length (hash-keys H))
→ 10827 ;; # of entries in cache
</syntaxhighlight>
=={{header|FreeBASIC}}==
<syntaxhighlight lang="freebasic">#define PesoMax 400
#define items 22
#define Tabu Chr(9)
Type Knapsack
articulo As String*22
peso As Integer
valor As Integer
pieza As Integer
End Type
Dim item(1 To 22) As Knapsack => { _
("map ", 9, 150, 0), ("compass ", 13, 35, 0), _
("water ", 153, 200, 0), ("sandwich ", 50, 160, 0), _
("glucose ", 15, 60, 0), ("tin ", 68, 45, 0), _
("banana ", 27, 60, 0), ("apple ", 39, 40, 0), _
("cheese ", 23, 30, 0), ("beer ", 52, 10, 0), _
("suntan cream ", 11, 70, 0), ("camera ", 32, 30, 0), _
("T-shirt ", 24, 15, 0), ("trousers ", 48, 10, 0), _
("umbrella ", 73, 40, 0), ("waterproof trousers ", 42, 70, 0), _
("waterproof overclothes", 43, 75, 0), ("note-case ", 22, 80, 0), _
("sunglasses ", 7, 20, 0), ("towel ", 18, 12, 0), _
("socks ", 4, 50, 0), ("book ", 30, 10, 0)}
Dim As Integer i, tot = 0, TValor = 0
For i =1 To Ubound(item)
tot += item(i).peso
Next i
Dim As Integer TPeso = tot-PesoMax
Dim As String pr = ""
Dim As Integer c = 0, v, w, k
Do
v = 1e9 : w = 0 : k = 0
For i = 1 To items
If item(i).pieza = 0 Then
w = 1000 * item(i).valor / item(i).peso
If w < v Then v = w : k = i
End If
Next i
If k Then
TPeso -= item(k).peso
item(k).pieza = 1
If TPeso <= 0 Then Exit Do
End If
c += 1
Loop Until c>= items
Print "Knapsack contents: "
For i = 1 To items
If item(i).pieza = 0 Then
Print item(i).articulo & Tabu & item(i).peso & Tabu & item(i).valor
TValor += item(i).valor
End If
Next i
Print !"\nTotal value: "; TValor
Print "Total weight: "; PesoMax + TPeso
Sleep</syntaxhighlight>
{{out}}
<pre>Knapsack contents:
map 9 150
compass 13 35
water 153 200
sandwich 50 160
glucose 15 60
banana 27 60
suntan cream 11 70
waterproof trousers 42 70
waterproof overclothes 43 75
note-case 22 80
sunglasses 7 20
socks 4 50
Total value: 1030
Total weight: 396</pre>
=={{header|Go}}==
Solution with caching.
<
import "fmt"
Line 1,231 ⟶ 1,311:
}
fmt.Printf("Value: %d; weight: %d\n", v, w)
}</
(A simple test and benchmark used while making changes to make sure performance wasn't sacrificed is available at [[/Go_test]].)
{{out}}
Line 1,250 ⟶ 1,330:
=={{header|Groovy}}==
Solution: dynamic programming
<
def totalValue = { list -> list.collect{ it.item.value * it.count }.sum() }
Line 1,267 ⟶ 1,347:
}
m[n][400]
}</
Test:
<
[name:"map", weight: 9, value:150, pieces:1],
[name:"compass", weight: 13, value: 35, pieces:1],
Line 1,304 ⟶ 1,384:
printf (' item: %-22s weight:%4d value:%4d count:%2d\n',
it.item.name, it.item.weight, it.item.value, it.count)
}</
{{out}}
<pre>Elapsed Time: 0.603 s
Line 1,323 ⟶ 1,403:
=={{header|Haskell}}==
Directly lifted from 1-0 problem:
<
("glucose",15,60,2), ("tin",68,45,3), ("banana",27,60,3), ("apple",39,40,3),
("cheese",23,30,1), ("beer",52,10,3), ("cream",11,70,1), ("camera",32,30,1),
Line 1,337 ⟶ 1,417:
new = map (\(val,itms)->(val + v * i, (name,i):itms)) old
main = print $ (knapsack inv) !! 400</
{{out}}
Line 1,344 ⟶ 1,424:
</pre>
The above uses merging lists for cache. It's faster, and maybe easier to understand when some constant-time lookup structure is used for cache (same output):
<
-- snipped the item list; use the one from above
Line 1,354 ⟶ 1,434:
prepend (x,n) (y,s) = (x+y,n:s)
main = do print $ knapsack inv 400</
=={{header|J}}==
Brute force solution:
<
'map'; 9 150 1
'compass'; 13 35 1
Line 1,407 ⟶ 1,487:
bestCombo''
978832641</
Interpretation of answer:
<
1 1 1 0 2 0 3 0 1 0 1 0 0 0 0 0 1 1 1 0 1 0
(0<decode 978832641) # (":,.decode 978832641),.' ',.names
Line 1,426 ⟶ 1,506:
396
values +/ .* decode 978832641
1010</
Dynamic programming solution (faster):
<
m=. 0$~1+400,+/pieces NB. maximum value cache
b=. m NB. best choice cache
Line 1,454 ⟶ 1,534:
dyn''
1 1 1 0 2 0 3 0 1 0 1 0 0 0 0 0 1 1 1 0 1 0</
Note: the brute force approach would return multiple "best answers" if more than one combination of choices would satisfy the "best" constraint. The dynamic approach arbitrarily picks one of those choices. That said, with this particular choice of item weights and values, this is an irrelevant distinction.
=={{header|Java}}==
General dynamic solution after [[wp:Knapsack_problem#0-1_knapsack_problem|wikipedia]]. The solution extends the method of [[Knapsack problem/0-1#Java ]].
<
import hu.pj.alg.BoundedKnapsack;
Line 1,541 ⟶ 1,621:
new BoundedKnapsackForTourists();
}
} // class</
<
import hu.pj.obj.Item;
Line 1,604 ⟶ 1,684:
setInitialStateForCalculation();
}
} // class</
<
import hu.pj.obj.Item;
Line 1,756 ⟶ 1,836:
solutionWeight = 0;
}
} // class</
<
public class Item {
Line 1,825 ⟶ 1,905:
public int getInKnapsack() {return inKnapsack;}
public int getBounding() {return bounding;}
} // class</
{{out}}
<pre>
Line 1,848 ⟶ 1,928:
=={{header|JavaScript}}==
Based on the (dynamic) J implementation. Expressed as an htm page:
<
<script type="text/javascript">
Line 1,926 ⟶ 2,006:
}
findBestPack();
</script></
This will generate (translating html to mediawiki markup):
{|
Line 1,997 ⟶ 2,077:
'''Works with gojq, the Go implementation of jq'''
<
def Item($name; $weight; $value; $count): {$name, $weight, $value, $count};
Line 2,085 ⟶ 2,165:
task(400)
</syntaxhighlight>
{{out}}
<pre>
Line 2,111 ⟶ 2,191:
'''Type and Function''':
<
struct KPDSupply{T<:Integer}
Line 2,139 ⟶ 2,219:
return pack
end
end</
'''Main''':
<
KPDSupply("compass", 13, 35, 1),
KPDSupply("water", 153, 200, 2),
Line 2,168 ⟶ 2,248:
println("The hiker should pack: \n - ", join(pack, "\n - "))
println("\nPacked weight: ", sum(getfield.(pack, :weight)), " kg")
println("Packed value: ", sum(getfield.(pack, :value)), " €")</
{{out}}
Line 2,189 ⟶ 2,269:
=={{header|Kotlin}}==
{{trans|C}}
<
data class Item(val name: String, val weight: Int, val value: Int, val count: Int)
Line 2,270 ⟶ 2,350:
println("--------------------- ------ ----- ------")
println("Items chosen $itemCount ${"%3d".format(sumWeight)} ${"%4d".format(sumValue)} ${"%2d".format(sumNumber)}")
}</
{{out}}
Line 2,292 ⟶ 2,372:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
LinearProgramming[-#[[;; , 3]], -{#[[;; , 2]]}, -{400},
{0, #[[4]]} & /@ #, Integers]} &@{{"map", 9, 150, 1},
Line 2,315 ⟶ 2,395:
{"towel", 18, 12, 2},
{"socks", 4, 50, 1},
{"book", 30, 10, 2}}</
{{Out}}
<pre>{{"map", 1}, {"compass", 1}, {"water", 1}, {"sandwich",
Line 2,326 ⟶ 2,406:
=={{header|Mathprog}}==
<
This model finds the integer optimal packing of a knapsack
Line 2,371 ⟶ 2,451:
;
end;</
The solution produced using glpk is here: [[Knapsack problem/Bounded/Mathprog]]
Line 2,380 ⟶ 2,460:
=={{header|MiniZinc}}==
<syntaxhighlight lang="minizinc">
%Solve Knapsack Problem Bounded. Nigel Galloway, Octoer 12th., 2020.
enum Items={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};
Line 2,393 ⟶ 2,473:
solve maximize wValue;
output[concat([let {string: g=show(take[n])} in "Take "++(if g==show(quantity[n]) then "all" else g endif)++" of \(n)\n" | n in Items where show(take[n])!="0"])++"\nTotal Weight=\(wTaken) Total Value="++show_float(4,2,wValue)]
</syntaxhighlight>
{{out}}
<pre>
Line 2,412 ⟶ 2,492:
=={{header|Nim}}==
We expand the list of items and apply the 0-1 algorithm.
<
import strformat
Line 2,520 ⟶ 2,600:
echo "Total weight: ", weight
echo "Total value: ", value
</syntaxhighlight>
{{out}}
Line 2,574 ⟶ 2,654:
=={{header|OxygenBasic}}==
<
type KnapSackItem string name,sys dag,value,tag
Line 2,685 ⟶ 2,765:
'
'Weight: 396
</syntaxhighlight>
=={{header|Oz}}==
Using constraint programming.
<
%% maps items to tuples of
%% Weight(hectogram), Value and available Pieces
Line 2,757 ⟶ 2,837:
{System.printInfo "\n"}
{System.showInfo "total value: "#{Value Best}}
{System.showInfo "total weight: "#{Weight Best}}</
{{out}}
<pre>
Line 2,777 ⟶ 2,857:
</pre>
Takes about 3 seconds on a slow netbook.
=={{header|Pascal}}==
{{works with|FPC}}
Dynamic programming solution (tested with FPC 3.2.2).
<syntaxhighlight lang="pascal">
program KnapsackBounded;
{$mode objfpc}{$j-}
uses
SysUtils, Math;
type
TItem = record
Name: string;
Weight, Value, Count: Integer;
end;
const
NUM_ITEMS = 22;
ITEMS: array[0..NUM_ITEMS-1] of TItem = (
(Name: 'map'; Weight: 9; Value: 150; Count: 1),
(Name: 'compass'; Weight: 13; Value: 35; Count: 1),
(Name: 'water'; Weight: 153; Value: 200; Count: 2),
(Name: 'sandwich'; Weight: 50; Value: 60; Count: 2),
(Name: 'glucose'; Weight: 15; Value: 60; Count: 2),
(Name: 'tin'; Weight: 68; Value: 45; Count: 3),
(Name: 'banana'; Weight: 27; Value: 60; Count: 3),
(Name: 'apple'; Weight: 39; Value: 40; Count: 3),
(Name: 'cheese'; Weight: 23; Value: 30; Count: 1),
(Name: 'beer'; Weight: 52; Value: 10; Count: 3),
(Name: 'suntan cream'; Weight: 11; Value: 70; Count: 1),
(Name: 'camera'; Weight: 32; Value: 30; Count: 1),
(Name: 'T-shirt'; Weight: 24; Value: 15; Count: 2),
(Name: 'trousers'; Weight: 48; Value: 10; Count: 2),
(Name: 'umbrella'; Weight: 73; Value: 40; Count: 1),
(Name: 'waterproof trousers'; Weight: 42; Value: 70; Count: 1),
(Name: 'waterproof overclothes'; Weight: 43; Value: 75; Count: 1),
(Name: 'note-case'; Weight: 22; Value: 80; Count: 1),
(Name: 'sunglasses'; Weight: 7; Value: 20; Count: 1),
(Name: 'towel'; Weight: 18; Value: 12; Count: 2),
(Name: 'socks'; Weight: 4; Value: 50; Count: 1),
(Name: 'book'; Weight: 30; Value: 10; Count: 2)
);
MAX_WEIGHT = 400;
var
D: array of array of Integer; //DP matrix
I, W, V, C, MaxWeight: Integer;
begin
SetLength(D, NUM_ITEMS + 1, MAX_WEIGHT + 1);
for I := 0 to High(ITEMS) do
for W := 0 to MAX_WEIGHT do begin
D[I+1, W] := D[I, W];
for C := 1 to ITEMS[I].Count do begin
if ITEMS[I].Weight * C > W then break;
V := D[I, W - ITEMS[I].Weight * C] + ITEMS[I].Value * C;
if V > D[I+1, W] then
D[I+1, W] := V;
end;
end;
W := MAX_WEIGHT;
MaxWeight := 0;
WriteLn('bagged:');
for I := High(ITEMS) downto 0 do begin
V := D[I+1, W];
C := 0;
while V <> D[I, W] + ITEMS[I].Value * C do begin
Dec(W, ITEMS[I].Weight);
Inc(C);
end;
Inc(MaxWeight, C * ITEMS[I].Weight);
if C <> 0 then
WriteLn(' ', C, ' ', ITEMS[I].Name);
end;
WriteLn('value = ', D[NUM_ITEMS, MAX_WEIGHT]);
WriteLn('weight = ', MaxWeight);
end.
</syntaxhighlight>
{{out}}
<pre>
bagged:
1 socks
1 sunglasses
1 note-case
1 waterproof overclothes
1 suntan cream
1 cheese
3 banana
2 glucose
1 water
1 compass
1 map
value = 1010
weight = 396
</pre>
=={{header|Perl}}==
Recursive solution with caching.
<
use strict;
Line 2,852 ⟶ 3,027:
}
}
print "Value: $v; Weight: $w\n";</
{{out}}
<pre>1 of map
Line 2,870 ⟶ 3,045:
===Very dumb and very slow brute force version===
Of no practical use, except for comparison against improvements.
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
Line 2,936 ⟶ 3,111:
<span style="color: #008080;">if</span> <span style="color: #000000;">points</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- sanity check</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Value %d, weight %g [%3.2fs]\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">points</span><span style="color: #0000FF;">,</span><span style="color: #000000;">weight</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">})</span>
<!--</
{{out}}
<pre>
Line 2,955 ⟶ 3,130:
Much faster but limited to integer weights
{{trans|C}}
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">items</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span>
Line 3,033 ⟶ 3,208:
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%-22s %5d %5d %5d\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"count, weight, points:"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tc</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tw</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tv</span><span style="color: #0000FF;">})</span>
<!--</
{{out}}
<pre>
Line 3,055 ⟶ 3,230:
duplicate solutions for w=15.783, 15.784, 15.785, and everything in between.
Using a (bespoke) range cache solves this problem, although the simplistic version given could probably be improved with a binary search or similar. It also significantly reduces the workload; for instance if you find a solution for 170 that actually weighs 150 then any subsequent query in 150..170 requires zero work, unlike the naive cache and dp solutions.
<!--<
<span style="color: #000080;font-style:italic;">-- demo\rosetta\knapsackB.exw</span>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
Line 3,197 ⟶ 3,372:
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"cache_entries:%d, hits:%d, misses:%d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">cache_entries</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cache_hits</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cache_misses</span><span style="color: #0000FF;">})</span>
<!--</
{{out}}
<pre>
Line 3,229 ⟶ 3,404:
=={{header|Picat}}==
<
go =>
Line 3,309 ⟶ 3,484:
["socks", 4, 50, 1],
["book", 30, 10, 2]],
MaxWeight = 400.</
{{out}}
Line 3,330 ⟶ 3,505:
=={{header|PicoLisp}}==
<
("map" 9 150 1) ("compass" 13 35 1)
("water" 153 200 3) ("sandwich" 50 60 2)
Line 3,361 ⟶ 3,536:
(for I K
(apply tab I (3 -24 6 6) NIL) )
(tab (27 6 6) NIL (sum cadr K) (sum caddr K)) )</
{{out}}
<pre> map 9 150
Line 3,384 ⟶ 3,559:
{{libheader|clpfd}}
Library clpfd is written by <b>Markus Triska</b>. Takes about 3 seconds to compute the best solution.
<
% tuples (name, weights, value, nb pieces).
Line 3,459 ⟶ 3,634:
sformat(W3, A3, [V]),
format('~w~w~w~w~n', [W0,W1,W2,W3]),
print_results(A1, A2, A3, T, TR, WM, VM).</
{{out}}
<pre> ?- knapsack.
Line 3,479 ⟶ 3,654:
===Library simplex===
Library simplex is written by <b>Markus Triska</b>. Takes about 10 seconds to compute the best solution.
<
% tuples (name, weights, value, pieces).
knapsack :-
Line 3,558 ⟶ 3,733:
W2 is W1 + X * W,
V2 is V1 + X * V),
print_results(S, A1, A2, A3, T, TN, W2, V2).</
=={{header|Python}}==
Not as [[Knapsack problem/0-1#Python|dumb a search]] over all possible combinations under the maximum allowed weight:
<
from collections import namedtuple
Line 3,612 ⟶ 3,787:
print("Bagged the following %i items" % len(bagged[COMB]))
print('\n\t'.join('%i off: %s' % (len(list(grp)), item.name) for item, grp in groupby(sorted(bagged[COMB]))))
print("for a total value of %i and a total weight of %i" % bagged[1:])</
{{out}}
<pre>Bagged the following 14 items
Line 3,629 ⟶ 3,804:
===Dynamic programming solution===
This is much faster. It expands the multiple possible instances of an item into individual instances then applies the zero-one dynamic knapsack solution:
<
try:
Line 3,694 ⟶ 3,869:
for item,grp in groupby(sorted(bagged))))
print("for a total value of %i and a total weight of %i" % (
sum(item[2] for item in bagged), sum(item[1] for item in bagged)))</
===Non-zero-one solution===
<
"sandwich": (50, 60, 2),
"map": (9, 150, 1),
Line 3,754 ⟶ 3,929:
w = w + items[name][0] * cnt
print("Total weight:", w, "Value:", v)</
=={{header|R}}==
Reading in task via web scraping.
<
library(rvest)
Line 3,769 ⟶ 3,944:
mutate(weight= as.numeric(weight),
value= as.numeric(value),
pieces= as.numeric(pieces))</
Solution of the task using genetic algorithm.
<
fitness= function(x= rep(1, nrow(task_table))){
Line 3,794 ⟶ 3,969:
cat("Weight:", sum(task_table$weight * evolution$par), "dag", "\n")
data.frame(item= task_table$items, pieces= as.integer(solution)) %>%
filter(solution> 0)</
{{out}}
Line 3,819 ⟶ 3,994:
The algorithm is nearly a direct translation of Haskell's array-based implementation. However, the data is taken from the webpage itself.
<syntaxhighlight lang="racket">
#lang racket
(require net/url html xml xml/path)
Line 3,908 ⟶ 4,083:
(match-let ([(solution value choices) (best (vector->list (solution-vector capacity)))])
(solution value (filter (compose positive? choice-count) choices))))
</syntaxhighlight>
{{out}}
Line 3,933 ⟶ 4,108:
Recursive algorithm, with cache. Idiomatic code style, using multi-subs and a class.
{{works with|Rakudo|2017.01}}
<syntaxhighlight lang="raku"
multi sub pokem ([], $, $v = 0) { $v }
Line 3,986 ⟶ 4,161:
for %hash.sort -> $item {
say " {$item.value} {$item.key}";
}</
{{out}}
<pre>Value = 1010
Line 4,005 ⟶ 4,180:
==== Faster alternative ====
Also recursive, with cache, but substantially faster. Code more generic (ported from Perl solution).
<syntaxhighlight lang="raku"
map 9 150 1
compass 13 35 1
Line 4,059 ⟶ 4,234:
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";</
{{out}}
<pre>1 of map
Line 4,080 ⟶ 4,255:
<br>"unrolled" and converted into discrete combination checks (based on the number of items). The unused combinatorial
<br>checks were discarded and only the pertinent code was retained.
<
call @gen /*generate items and initializations. */
call @sort /*sort items by decreasing their weight*/
Line 4,235 ⟶ 4,410:
do j37=j36+(j36>0) to h;if w.j37+w36>m then iterate j36;w37=w36+w.j37;z37=z36+v.j37;if z37>$ then call j? 37
end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end
end;end;end;end;end;end;end;end;end;end; return /* [↑] there is one END for each DO loop.*/</
'''output'''
<pre>
Line 4,294 ⟶ 4,469:
{{trans|Python}}
<
# Item struct to represent each item in the problem
Struct.new('Item', :name, :weight, :value, :count)
Line 4,354 ⟶ 4,529:
p "Total weight: #{w}, Value: #{val}"
</syntaxhighlight>
=={{header|SAS}}==
Use MILP solver in SAS/OR:
<
data mydata;
input item $1-23 weight value pieces;
Line 4,408 ⟶ 4,583:
print TotalValue;
print {i in ITEMS: NumSelected[i].sol > 0.5} NumSelected;
quit;</
Output:
Line 4,431 ⟶ 4,606:
=={{header|Sidef}}==
{{trans|Perl}}
<
map 9 150 1
compass 13 35 1
Line 4,497 ⟶ 4,672:
say "#{p[i]} of #{items[i].name}" if p[i].is_pos
}
say "Value: #{v}; Weight: #{w}"</
{{out}}
<pre>
Line 4,518 ⟶ 4,693:
{{trans|Python}}
<
public var name: String
public var weight: Int
Line 4,599 ⟶ 4,774:
}
print("For a total value of \(totalVal) and weight of \(totalWeight)")</
{{out}}
Line 4,623 ⟶ 4,798:
=={{header|Tcl}}==
Classic dumb search algorithm:
<
set items {
{map 9 150 1}
Line 4,709 ⟶ 4,884:
foreach {count item} [countednames $best] {
puts "\t$count * $item"
}</
{{out}}
<pre>
Line 4,730 ⟶ 4,905:
Instead of an ''ad-hoc'' solution, we can convert this task to a
[[wp:Mixed_integer_programming#Integer_unknowns|mixed integer programming]] problem instance and solve it with the [http://lpsolve.sourceforge.net lpsolve] library, which is callable in Ursala.
<
#import flo
#import lin
Line 4,773 ⟶ 4,948:
#show+
main = format solution system items</
The <code>linear_system$[</code>...<code>]</code> function takes the item list as an argument and returns a data structure with the following fields, which is passed to the <code>solution</code> function, which calls the <code>lpsolve</code> routines.
* <code>integers</code> declares that all variables in the list take integer values
Line 4,797 ⟶ 4,972:
{{trans|Kotlin}}
{{libheader|Wren-fmt}}
<
class Item {
Line 4,889 ⟶ 5,064:
}
System.print("--------------------- ------ ----- ------")
Fmt.print("Items chosen $d $3d $4d $2d", itemCount, sumWeight, sumValue, sumNumber)</
{{out}}
Line 4,912 ⟶ 5,087:
=={{header|zkl}}==
{{trans|Haskell}}
<
[1..c].reduce(fcn(list,i,nm,w,v,old){
wi,left,right:=w*i,list[0,wi],list[wi,*];
Line 4,919 ⟶ 5,094:
fcn([(v1,_)]a,[(v2,_)]b){ v1>v2 and a or b },new));
},old,nm,w,v,old);
}//--> new list</
<
T("apple", 39, 40,3),T("banana", 27,60,3),
T("beer", 52, 10,3),T("book", 30,10,2),T("camera", 32, 30,1),
Line 4,933 ⟶ 5,108:
'wrap(nm,n){ items[items.filter1n(fcn(it,nm){ it[0]==nm },nm)][1]*n })
.sum(0)
};</
<
knapsack:=items.reduce(addItem,(MAX_WEIGHT).pump(List,T(0,T).copy))[-1];
knapsack.toString(*).println(weight(knapsack));</
{{out}}
<pre>
| |||