Knapsack problem/0-1: Difference between revisions
→{{header|FORTRAN}}
m (→{{header|QB64}}: syntax hi-lighting, formatting) |
Bwana Pete (talk | contribs) |
||
| (26 intermediate revisions by 11 users not shown) | |||
Line 92:
{{trans|Python}}
<
V totwt = 0
V totval = 0
Line 133:
print("Bagged the following items\n "sorted(bagged.map((item, _, _2) -> item)).join("\n "))
V (val, wt) = totalvalue(bagged)
print(‘for a total value of #. and a total weight of #.’.format(val, -wt))</
{{out}}
Line 155:
=={{header|360 Assembly}}==
Non recurvive brute force version.
<
KNAPSA01 CSECT
USING KNAPSA01,R13
Line 278:
DATAE DC 0C
YREGS
END KNAPSA01</
{{out}}
<pre>
Line 298:
=={{header|Ada}}==
<
with Ada.Strings.Unbounded;
Line 406:
end if;
end loop;
end Knapsack_01;</
{{out}}
<pre>
Line 427:
=={{header|APL}}==
<
[1] total←400
[2] list←("map" 9 150)("compass" 13 35)("water" 153 200)("sandwich" 50 160)("glucose" 15 60) ("tin" 68 45)("banana" 27 60)("apple" 39 40)("cheese" 23 30)("beer" 52 10) ("suntan cream" 11 70)("camera" 32 30)("t-shirt" 24 15)("trousers" 48 10) ("umbrella" 73 40)("waterproof trousers" 42 70)("waterproof overclothes" 43 75) ("note-case" 22 80) ("sunglasses" 7 20) ("towel" 18 12) ("socks" 4 50) ("book" 30 10)
Line 439:
[10] :end
[11] ret←⊃ret,⊂'TOTALS:' (+/2⊃¨ret)(+/3⊃¨ret)
∇</
{{out}}
<pre>
Line 461:
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f KNAPSACK_PROBLEM_0-1.AWK
BEGIN {
Line 505:
exit(0)
}
</syntaxhighlight>
{{out}}
<pre>
Line 528:
{{works with|QuickBasic|4.5}}
{{trans|QB64}}
<
RANDOMIZE TIMER
DIM L(N), C(N), j(N), q(a), d(a), q$(a)
Line 563:
IF d(i) <= G AND q(i) > max THEN max = q(i): h = i
NEXT i
PRINT d(h), q(h), q$(h)</
{{out}}
<pre>Same as QB64 entry.</pre>
Line 569:
==={{header|Yabasic}}===
{{trans|QB64}}
<
dim L(N), C(N), j(N), q(a), d(a), q$(a)
Line 604:
next i
print d(h), chr$(9), q(h), chr$(9), q$(h)
end</
{{out}}
<pre>Same as QB64 entry
https://jdoodle.com/iembed/v0/suj</pre>
=={{header|Batch File}}==
<
:: Initiate command line environment
@echo off
Line 677:
echo Total Value: %totalimportance% Total Weight: %totalweight%
pause>nul
</syntaxhighlight>
{{out}}
Line 687:
=={{header|BBC BASIC}}==
{{works with|BBC BASIC for Windows}}
<
nItems% = 22
maxWeight% = 400
Line 751:
m{(index%)} = excluded{}
ENDIF
= index%</
{{out}}
<pre>
Line 772:
=={{header|Bracmat}}==
<
( things
= (map.9.150)
Line 837:
& out$(!maxvalue.!sack));
!knapsack;</
{{out}}
<
. map
compass
Line 851:
note-case
sunglasses
socks</
=={{header|C}}==
<
#include <stdlib.h>
Line 933:
return 0;
}
</syntaxhighlight>
{{out}}
<pre>
Line 954:
{{libheader|System}}
{{libheader|System.Collections.Generic}}
<
using System.Collections.Generic;
Line 1,095:
}
}
}</
("Bag" might not be the best name for the class, since "bag" is sometimes also used to refer to a multiset data structure.)
===C#, Alternative Version===
C# Knapsak 0-1 Russian Binary ciphers
Line 1,109:
Random values origin are automatically assigned create integral of quantity and quality
<
using System.Text; // rextester.com/YRFA61366
namespace Knapsack
Line 1,180:
}
}
}</
{{out}}
Line 1,212:
=== First version ===
{{libheader|Boost}}
<
#include <string>
#include <iostream>
Line 1,309:
bestItems.swap( solutionSets[ n - 1][ weightlimit - 1 ] ) ;
return bestValues[ n - 1 ][ weightlimit - 1 ] ;
}</
{{out}}
<pre>
Line 1,331:
=== Second version ===
{{Works with|C++17}}
<
#include <iostream>
#include <set>
Line 1,406:
std::cout << std::endl << std::setw(24) << "total:" << std::setw(6) << totalweight << std::setw(6) << bestValue << std::endl;
return 0;
}</
{{Out}}
<pre> best knapsack:
Line 1,426:
=={{header|C_sharp}}==
All combinations, eight threads, break when weight is to large.
<
using System.Threading.Tasks;
class Program
Line 1,476:
"waterproof trousers","waterproof overclothes",
"note-case","sunglasses","towel","socks","book"};
}</
A dynamic version.
<
class program
{
Line 1,521:
"waterproof trousers","waterproof overclothes",
"note-case","sunglasses","towel","socks","book"};
}</
=={{header|Ceylon}}==
Line 1,528:
<b>module.ceylon</b>:
<
module knapsack "1.0.0" {
}
</syntaxhighlight>
<b>run.ceylon:</b>
<
shared void run() {
value knapsack = pack(items, empty(400));
Line 1,618:
then packRecursive(sortedItems.rest, add(firstItem,knapsack))
else knapsack;
</syntaxhighlight>
Line 1,644:
Uses the dynamic programming solution from [[wp:Knapsack_problem#0-1_knapsack_problem|Wikipedia]].
First define the ''items'' data:
<
[ "map" 9 150
"compass" 13 35
Line 1,670:
(defstruct item :name :weight :value)
(def items (vec (map #(apply struct item %) (partition 3 item-data))))</
''m'' is as per the Wikipedia formula, except that it returns a pair ''[value indexes]'' where ''indexes'' is a vector of index values in ''items''. ''value'' is the maximum value attainable using items 0..''i'' whose total weight doesn't exceed ''w''; ''indexes'' are the item indexes that produces the value.
<
(defn m [i w]
Line 1,688:
no))))))
(def mm (memoize m))</
Call ''m'' and print the result:
<
(let [[value indexes] (m (-> items count dec) 400)
Line 1,696:
(println "items to pack:" (join ", " names))
(println "total value:" value)
(println "total weight:" (reduce + (map (comp :weight items) indexes))))</
{{out}}
<pre>items to pack: map, compass, water, sandwich, glucose, banana, suntan cream, waterproof trousers,
Line 1,705:
=={{header|Common Lisp}}==
Cached method.
<
(defmacro mm-set (p v) `(if ,p ,p (setf ,p ,v)))
Line 1,734:
(T-shirt 24 15) (trousers 48 10) (umbrella 73 40)
(trousers 42 70) (overclothes 43 75) (notecase 22 80)
(glasses 7 20) (towel 18 12) (socks 4 50) (book 30 10))))</
{{out}}
<pre>(1030 396
Line 1,743:
=={{header|Crystal}}==
Branch and bound solution
<
struct BitArray
Line 1,829:
puts "total weight #{used.sum(&.weight)}, total value #{used.sum(&.value)}"
puts "checked nodes: #{solver.checked_nodes}"
</syntaxhighlight>
{{out}}
<pre>optimal choice: ["map", "socks", "suntan cream", "glucose", "note-case", "sandwich", "sunglasses", "compass", "banana", "waterproof overclothes", "waterproof trousers", "water"]
Line 1,838:
===Dynamic Programming Version===
{{trans|Python}}
<
struct Item { string name; int weight, value; }
Line 1,882:
const t = reduce!q{ a[] += [b.weight, b.value] }([0, 0], bag);
writeln("\nTotal weight and value: ", t[0] <= limit ? t : [0, 0]);
}</
{{out}}
<pre>Items:
Line 1,902:
===Brute Force Version===
{{trans|C}}
<
immutable Item[] items = [
Line 1,957:
}
writefln("\nTotal value: %d; weight: %d", s.value, w);
}</
The runtime is about 0.09 seconds.
{{out}}
Line 1,978:
===Short Dynamic Programming Version===
{{trans|Haskell}}
<
struct Item { string name; int w, v; }
Line 1,999:
void main() {
reduce!addItem(Pair().repeat.take(400).array, items).back.writeln;
}</
Runtime about 0.04 seconds.
{{out}}
<pre>Tuple!(int, "tot", string[], "names")(1030, ["banana", "compass", "glucose", "map", "note-case", "sandwich", "socks", "sunglasses", "suntan cream", "water", "overclothes", "waterproof trousers"])</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
This is a good example of using an iterator. The problem involves looking at all different compinations of items in the list. If you increment a number up to a certain maximum, you systematically set all combination of bits in that number. The trick is turning the pattern of bits in a number into indices into the packing list. The iterater handles that and so it can be used in multiple places in the code to step through various the combinations of items in the list.
<syntaxhighlight lang="Delphi">
{Item to store data in}
type TPackItem = record
Name: string;
Weight,Value: integer;
end;
{List of items, weights and values}
const ItemsList: array [0..21] of TPackItem = (
(Name: 'map'; Weight: 9; Value: 150),
(Name: 'compass'; Weight: 13; Value: 35),
(Name: 'water'; Weight: 153; Value: 200),
(Name: 'sandwich'; Weight: 50; Value: 160),
(Name: 'glucose'; Weight: 15; Value: 60),
(Name: 'tin'; Weight: 68; Value: 45),
(Name: 'banana'; Weight: 27; Value: 60),
(Name: 'apple'; Weight: 39; Value: 40),
(Name: 'cheese'; Weight: 23; Value: 30),
(Name: 'beer'; Weight: 52; Value: 10),
(Name: 'suntan cream'; Weight: 11; Value: 70),
(Name: 'camera'; Weight: 32; Value: 30),
(Name: 't-shirt'; Weight: 24; Value: 15),
(Name: 'trousers'; Weight: 48; Value: 10),
(Name: 'umbrella'; Weight: 73; Value: 40),
(Name: 'waterproof trousers'; Weight: 42; Value: 70),
(Name: 'waterproof overclothes'; Weight: 43; Value: 75),
(Name: 'note-case'; Weight: 22; Value: 80),
(Name: 'sunglasses'; Weight: 7; Value: 20),
(Name: 'towel'; Weight: 18; Value: 12),
(Name: 'socks'; Weight: 4; Value: 50),
(Name: 'book'; Weight: 30; Value: 10));
{Iterater object to step through all the indices
{ corresponding to the bits in "N". This is used }
{ step through all the combinations of items }
type TBitIterator = class(TObject)
private
FNumber,FIndex: integer;
public
procedure Start(StartNumber: integer);
function Next(var Index: integer): boolean;
end;
procedure TBitIterator.Start(StartNumber: integer);
{Set the starting value of the number }
begin
FNumber:=StartNumber;
end;
function TBitIterator.Next(var Index: integer): boolean;
{Return the next available index}
begin
Result:=False;
while FNumber>0 do
begin
Result:=(FNumber and 1)=1;
if Result then Index:=FIndex;
FNumber:=FNumber shr 1;
Inc(FIndex);
if Result then break;
end;
end;
{=============================================================================}
procedure GetSums(N: integer; var Weight,Value: integer);
{Iterate through all indices corresponding to N}
{Get get the sum of their values}
var Inx: integer;
var BI: TBitIterator;
begin
BI:=TBitIterator.Create;
try
BI.Start(N);
Weight:=0; Value:=0;
while BI.Next(Inx) do
begin
Weight:=Weight+ItemsList[Inx].Weight;
Value:=Value+ItemsList[Inx].Value;
end;
finally BI.Free; end;
end;
procedure DoKnapsackProblem(Memo: TMemo);
{Find optimized solution to Knapsack problem}
{By iterating through all binary combinations}
var I,J,Inx: integer;
var Max: integer;
var WeightSum,ValueSum: integer;
var BestValue,BestIndex,BestWeight: integer;
var S: string;
var BI: TBitIterator;
begin
BI:=TBitIterator.Create;
try
{Get value that will cover all binary combinations}
Max:=1 shl Length(ItemsList)-1;
BestValue:=0;
{Iterate through all combinations of bits}
for I:=1 to Max do
begin
{Get the sum of the weights and values}
GetSums(I,WeightSum,ValueSum);
{Ignore any weight greater than 400}
if WeightSum>400 then continue;
{Test if this is the best value so far}
if ValueSum>BestValue then
begin
BestValue:=ValueSum;
BestWeight:=WeightSum;
BestIndex:=I;
end;
end;
{Display the best result}
Memo.Lines.Add(' Item Weight Value');
Memo.Lines.Add('---------------------------------------');
BI.Start(BestIndex);
while BI.Next(Inx) do
begin
S:=' '+Format('%-25s',[ItemsList[Inx].Name]);
S:=S+Format('%5d',[ItemsList[Inx].Weight]);
S:=S+Format('%7d',[ItemsList[Inx].Value]);
Memo.Lines.Add(S);
end;
Memo.Lines.Add('---------------------------------------');
Memo.Lines.Add(Format('Total %6d %6d',[BestWeight,BestValue]));
Memo.Lines.Add('Best Inx: '+IntToStr(BestIndex));
Memo.Lines.Add('Best Value: '+IntToStr(BestValue));
Memo.Lines.Add('Best Weight: '+IntToStr(BestWeight));
finally BI.Free; end;
end;
</syntaxhighlight>
{{out}}
<pre>
Item Weight Value
---------------------------------------
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 396 1030
Best Inx: 1541215
Best Value: 1030
Best Weight: 396
</pre>
=={{header|Dart}}==
<
int MIN_VALUE=-100;
int N = items.length; // number of items
Line 2,108 ⟶ 2,275:
print("Elapsed Time = ${sw.elapsedInMs()}ms");
}</
{{out}}
<pre>[item, profit, weight]
Line 2,128 ⟶ 2,295:
=={{header|EasyLang}}==
<syntaxhighlight lang="text">
name$[] = [ "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" ]
weight[] = [ 9 13 153 50 15 68 27 39 23 52 11 32 24 48 73 42 43 22 7 18 4 30 ]
value[] = [ 150 35 200 160 60 45 60 40 30 10 70 30 15 10 40 70 75 80 20 12 50 10 ]
max_w = 400
#
if i <= 0
wres = 0
vres = 0
items[] = [ ]
elif weight[i] >
else
v1 += value[i]
if v1 > vres
swap items[] items1[]
items[] &= i
wres = w1 + weight[i]
vres = v1
.
.
.
print "weight: " & w
print "value: " & v
print "items:"
for
print " " & name$[
.
</syntaxhighlight>
=={{header|EchoLisp}}==
<
(require 'struct)
(require 'hash)
Line 2,196 ⟶ 2,365:
(set! restant (- restant (poids i)))
(name i)))
</syntaxhighlight>
{{out}}
<
;; init table
(define goodies
Line 2,219 ⟶ 2,388:
(length (hash-keys H))
→ 4939 ;; number of entries "i | weight" in hash table
</syntaxhighlight>
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
class
APPLICATION
Line 2,263 ⟶ 2,432:
end
</syntaxhighlight>
<syntaxhighlight lang="eiffel">
class
ITEM
Line 2,300 ⟶ 2,469:
end
</syntaxhighlight>
<syntaxhighlight lang="eiffel">
class
KNAPSACKZEROONE
Line 2,408 ⟶ 2,577:
end
</syntaxhighlight>
{{out}}
<pre>
Line 2,429 ⟶ 2,598:
=={{header|Elixir}}==
{{trans|Erlang}}
<
def solve([], _total_weight, item_acc, value_acc, weight_acc), do:
{item_acc, value_acc, weight_acc}
Line 2,489 ⟶ 2,658:
IO.puts "Time elapsed in milliseconds: #{time/1000}"
end
go.(stuff, max_weight)</
{{out}}
Line 2,515 ⟶ 2,684:
{{Trans|Common Lisp}} with changes (memoization without macro)
<
(defun ks (max-w items)
(let ((cache (make-vector (1+ (length items)) nil)))
Line 2,550 ⟶ 2,719:
(waterproof-trousers 42 70) (overclothes 43 75) (notecase 22 80)
(glasses 7 20) (towel 18 12) (socks 4 50) (book 30 10)))
</syntaxhighlight>
{{out}}
Line 2,560 ⟶ 2,729:
Another way without cache :
<
(defun best-rate (l1 l2)
"predicate for sorting a list of elements regarding the value/weight rate"
Line 2,608 ⟶ 2,777:
(waterproof-trousers 42 70) (overclothes 43 75) (notecase 22 80)
(glasses 7 20) (towel 18 12) (socks 4 50) (book 30 10)) 400)
</syntaxhighlight>
{{out}} with org-babel in Emacs
Line 2,630 ⟶ 2,799:
=={{header|Erlang}}==
<syntaxhighlight lang="erlang">
-module(knapsack_0_1).
Line 2,703 ⟶ 2,872:
HeadRes
end.
</syntaxhighlight>
{{out}}
Line 2,729 ⟶ 2,898:
=={{header|Euler Math Toolbox}}==
<syntaxhighlight lang="euler math toolbox">
>items=["map","compass","water","sandwich","glucose", ...
> "tin","banana","apple","cheese","beer","suntan creame", ...
Line 2,756 ⟶ 2,925:
sunglasses
socks
</syntaxhighlight>
=={{header|F_Sharp|F#}}==
===Using A* Algorithm===
<
//Solve Knapsack 0-1 using A* algorithm
//Nigel Galloway, August 3rd., 2018
Line 2,783 ⟶ 2,952:
if bv>=h then t else fN (fH zl (bv,t) zw zv zt)
fN (fH 0 (0.0,[]) 0.0 0.0 [])
</syntaxhighlight>
{{out}}
<
let itemsf = [
"map", 9.0, 150.0;
Line 2,809 ⟶ 2,978:
"socks", 4.0, 50.0;
"book", 30.0, 10.0;]|> List.sortBy(fun(_,n,g)->n/g)
</syntaxhighlight>
<pre>
> let x=knapStar itemsf 400.0;;
Line 2,833 ⟶ 3,002:
=={{header|Factor}}==
Using dynamic programming:
<
math.order math.parser math.ranges sequences sorting ;
IN: rosetta.knappsack.0-1
Line 2,909 ⟶ 3,078:
"Items packed: " print
natural-sort
[ " " write print ] each ;</
<pre>
( scratchpad ) main
Line 2,929 ⟶ 3,098:
=={{header|Forth}}==
<syntaxhighlight lang="forth">
\ Rosetta Code Knapp-sack 0-1 problem. Tested under GForth 0.7.3.
\ 22 items. On current processors a set fits nicely in one CELL (32 or 64 bits).
Line 3,000 ⟶ 3,169:
." Weight: " Sol @ [ END-SACK Sack ]sum . ." Value: " Sol @ [ END-SACK VAL + Sack VAL + ]sum .
;
</syntaxhighlight>
{{out}}
<pre>
Line 3,016 ⟶ 3,185:
socks
Weight: 396 Value: 1030
</pre>
# Numbered list item
=={{header|Fortran}}==
{{trans|Pascal}}
<syntaxhighlight lang="FORTRAN">
Program Knapsack01
! Translation of Pascal version on Rosetta Code.
implicit none
integer, parameter :: NUM_ITEMS = 22
integer, parameter :: MAX_WEIGHT = 400
type :: TItem
character(len=20) :: Name
integer :: Weight, Value
end type TItem
type(TItem), dimension(0:NUM_ITEMS-1) :: ITEMS
integer, dimension(0:NUM_ITEMS, 0:MAX_WEIGHT) :: D
integer :: I, W, V, MaxWeight
! Init Arrays
d = 0
ITEMS = [ TItem('compass', 13, 35), &
TItem('water', 153, 200), &
TItem('sandwich', 50, 160), &
TItem('glucose', 15, 60), &
TItem('tin', 68, 45), &
TItem('banana', 27, 60), &
TItem('apple', 39, 40), &
TItem('cheese', 23, 30), &
TItem('beer', 52, 10), &
TItem('suntan cream', 11, 70), &
TItem('camera', 32, 30), &
TItem('T-shirt', 24, 15), &
TItem('trousers', 48, 10), &
TItem('umbrella', 73, 40), &
TItem('waterproof trousers', 43, 70), &
TItem('waterproof overclothes', 42, 75), &
TItem('note-case', 22, 80), &
TItem('sunglasses', 7, 20), &
TItem('towel', 18, 12), &
TItem('map', 9, 150), &
TItem('socks', 4, 50), &
TItem('book', 30, 10) ]
!
do I = 0, NUM_ITEMS-1
do W = 0, MAX_WEIGHT
if (ITEMS(I)%Weight > W) then
D(I+1, W) = D(I, W)
else
D(I+1, W) = max(D(I, W), D(I, W - ITEMS(I)%Weight) + ITEMS(I)%Value)
end if
end do
end do
W = MAX_WEIGHT
V = D(NUM_ITEMS, W)
MaxWeight = 0
!
write(*, "(/,'bagged:')")
do I = NUM_ITEMS-1, 0, -1 !Pete
if (D(I+1, W) == V) then
if((D(I, (W - ITEMS(I)%Weight)) == V - ITEMS(I)%Value)) then
write(*, "(' ', A,t25,i0,t35,i0)", advance='yes') ITEMS(I)%Name,ITEMS(I)%weight,ITEMS(I)%value
MaxWeight = MaxWeight + ITEMS(I)%Weight
W = W - ITEMS(I)%Weight
V = V - ITEMS(I)%Value
end if
end if
end do
!
write(*, "('value = ', I0)") D(NUM_ITEMS, MAX_WEIGHT)
write(*, "('weight = ', I0)") MaxWeight
end program Knapsack01
</syntaxhighlight>
{{out}}
<pre>
bagged:
socks 4 50
map 9 150
sunglasses 7 20
note-case 22 80
waterproof overcloth 42 75
waterproof trousers 43 70
suntan cream 11 70
banana 27 60
glucose 15 60
sandwich 50 160
water 153 200
compass 13 35
value = 1030
weight = 396
knapsack time = 94 Milliseconds
</pre>
===Branch and Bound Version===
{{trans|Fortran 77}}
<syntaxhighlight lang="fortran">
module ksack2
!
! THIS SUBROUTINE SOLVES THE 0-1 SINGLE KNAPSACK PROBLEM
!
! MAXIMIZE Z = P(1)*X(1) + ... + P(N)*X(N)
!
! SUBJECT TO: W(1)*X(1) + ... + W(N)*X(N) .LE. C ,
! X(J) = 0 OR 1 FOR J=1,...,N.
!
! THE PROGRAM IS INCLUDED IN THE VOLUME
! S. MARTELLO, P. TOTH, "KNAPSACK PROBLEMS: ALGORITHMS
! AND COMPUTER IMPLEMENTATIONS", JOHN WILEY, 1990
! (https://dl.acm.org/doi/book/10.5555/98124)
! AND IMPLEMENTS THE BRANCH-AND-BOUND ALGORITHM DESCRIBED IN
! SECTION 2.5.2 .
! THE PROGRAM DERIVES FROM AN EARLIER CODE PRESENTED IN
! S. MARTELLO, P. TOTH, "ALGORITHM FOR THE SOLUTION OF THE 0-1 SINGLE
! KNAPSACK PROBLEM", COMPUTING, 1978.
! The orignal program was written in Fortran 77 and was an amazing tangle of GOTO statements.
! I have reworked the code in such a manner as to eliminate the GOTO statements and bring it
! to Fortran 2018 LANGUAGE compliance though the code logic remains somewhat untractable.
!
! The routine requires a large parameter string which includes 4 dummy arrays for it's calculations.
! As well, it offers an option to check the input data for correctness.
! Rather than modify the original algorithm, I wrote a simple wrapper called "start_knapsack" that
! allocates those arrays as well as defaulting the input parameter check to "on", hiding them from the user.
! Having said that, the algorithm works very well and is very fast. I've included it in this
! Rosetta Code listing because it scales well and can be used with a large dataset.
! Which a potential user may desire.
! Peter.kelly@acm.org (28-December-2023)
!
! THE INPUT PROBLEM MUST SATISFY THE CONDITIONS
!
! 1) 2 .LE. N .LE. JDIM - 1 ;
! 2) P(J), W(J), C POSITIVE INTEGERS;
! 3) MAX (W(J)) .LE. C ;
! 4) W(1) + ... + W(N) .GT. C ;
! 5) P(J)/W(J) .GE. P(J+1)/W(J+1) FOR J=1,...,N-1. <-- Note well. They need to be sorted in the greatest ratio of (p(j)/w(j)) down to the smallest one
!
! MT1 CALLS 1 PROCEDURE: CHMT1.
!
! MT1 NEEDS 8 ARRAYS ( P , W , X , XX , MIN , PSIGN , WSIGN
! AND ZSIGN ) OF LENGTH AT LEAST N + 1 .
!
! MEANING OF THE INPUT PARAMETERS:
! N = NUMBER OF ITEMS;
! P(J) = PROFIT OF ITEM J (J=1,...,N);
! W(J) = WEIGHT OF ITEM J (J=1,...,N);
! C = CAPACITY OF THE KNAPSACK;
! JDIM = DIMENSION OF THE 8 ARRAYS;
! JCK = 1 IF CHECK ON THE INPUT DATA IS DESIRED,
! = 0 OTHERWISE.
!
! MEANING OF THE OUTPUT PARAMETERS:
! Z = VALUE OF THE OPTIMAL SOLUTION IF Z .GT. 0 ,
! = ERROR IN THE INPUT DATA (WHEN JCK=1) IF Z .LT. 0 : CONDI-
! TION - Z IS VIOLATED;
! X(J) = 1 IF ITEM J IS IN THE OPTIMAL SOLUTION,
! = 0 OTHERWISE.
!
! ARRAYS XX, MIN, PSIGN, WSIGN AND ZSIGN ARE DUMMY.
!
! ALL THE PARAMETERS ARE INTEGER. ON RETURN OF MT1 ALL THE INPUT
! PARAMETERS ARE UNCHANGED.
!
implicit none
contains
subroutine mt1(n , p , w , c , z , x , jdim , jck , xx , min , psign , wsign , zsign)
implicit none
integer :: jdim
integer :: n
integer , intent(inout) , dimension(jdim) :: p
integer , intent(inout) , dimension(jdim) :: w
integer :: c
integer , intent(inout) :: z
integer , intent(out) , dimension(jdim) :: x
integer , intent(in) :: jck
integer , intent(inout) , dimension(jdim) :: xx
integer , intent(inout) , dimension(jdim) :: min
integer , intent(inout) , dimension(jdim) :: psign
integer , intent(inout) , dimension(jdim) :: wsign
integer , intent(inout) , dimension(jdim) :: zsign
!
real :: a
real :: b
integer :: ch
integer :: chs
integer :: diff
integer :: ii
integer :: ii1
integer :: in
integer :: ip
integer :: iu
integer :: j
integer :: j1
integer :: jj
integer :: jtemp
integer :: kk
integer :: lim
integer :: lim1
integer :: ll
integer :: lold
integer :: mink
integer :: n1
integer :: nn
integer :: profit
integer :: r
integer :: t
integer :: next_code_block
!*Code
next_code_block = 1
dispatch_loop: do
select case(next_code_block)
case(1)
z = 0
if( jck==1 )call chmt1(n , p , w , c , z , jdim)
if( z<0 )return
! INITIALIZE.
ch = c
ip = 0
chs = ch
first_loop: do ll = 1 , n
if( w(ll)>chs )exit first_loop
ip = ip + p(ll)
chs = chs - w(ll)
end do first_loop
ll = ll - 1
if( chs==0 )then
z = ip
x(1:ll) = 1
nn = ll + 1
x(nn:n) = 0
return
else
p(n + 1) = 0
w(n + 1) = ch + 1
lim = ip + chs*p(ll + 2)/w(ll + 2)
a = w(ll + 1) - chs
b = ip + p(ll + 1)
lim1 = b - a*float(p(ll))/float(w(ll))
if( lim1>lim )lim = lim1
mink = ch + 1
min(n) = mink
do j = 2 , n
kk = n + 2 - j
if( w(kk)<mink )mink = w(kk)
min(kk - 1) = mink
end do
xx(1:n) = 0
z = 0
profit = 0
lold = n
ii = 1
next_code_block = 4
cycle dispatch_loop
end if
case(2)
! TRY TO INSERT THE II-TH ITEM INTO THE CURRENT SOLUTION.
do while ( w(ii)>ch )
ii1 = ii + 1
if( z>=ch*p(ii1)/w(ii1) + profit )then
next_code_block = 5
cycle dispatch_loop
end if
ii = ii1
end do
! BUILD A NEW CURRENT SOLUTION.
ip = psign(ii)
chs = ch - wsign(ii)
in = zsign(ii)
ll = in
do while ( ll<=n )
if( w(ll)>chs )then
iu = chs*p(ll)/w(ll)
ll = ll - 1
if( iu==0 )then
next_code_block = 3
cycle dispatch_loop
end if
if( z>=profit + ip + iu )then
next_code_block = 5
cycle dispatch_loop
end if
next_code_block = 4
cycle dispatch_loop
else
ip = ip + p(ll)
chs = chs - w(ll)
end if
end do
ll = n
next_code_block = 3
case(3)
if( z>=ip + profit )then
next_code_block = 5
cycle dispatch_loop
end if
z = ip + profit
nn = ii - 1
x(1:nn) = xx(1:nn)
x(ii:ll) = 1
if( ll/=n )then
nn = ll + 1
x(nn:n) = 0
end if
if( z/=lim )then
next_code_block = 5
cycle dispatch_loop
end if
return
case(4)
! SAVE THE CURRENT SOLUTION.
wsign(ii) = ch - chs
psign(ii) = ip
zsign(ii) = ll + 1
xx(ii) = 1
nn = ll - 1
if( nn>=ii )then
do j = ii , nn
wsign(j + 1) = wsign(j) - w(j)
psign(j + 1) = psign(j) - p(j)
zsign(j + 1) = ll + 1
xx(j + 1) = 1
end do
end if
j1 = ll + 1
wsign(j1:lold) = 0
psign(j) = 0
zsign(j1:lold) = [(jtemp, jtemp = j1,lold)]
lold = ll
ch = chs
profit = profit + ip
if( ll<(n - 2) )then
ii = ll + 2
if( ch>=min(ii - 1) )then
next_code_block = 2
cycle dispatch_loop
end if
else if( ll==(n - 2) )then
if( ch>=w(n) )then
ch = ch - w(n)
profit = profit + p(n)
xx(n) = 1
end if
ii = n - 1
else
ii = n
end if
! SAVE THE CURRENT OPTIMAL SOLUTION.
if( z<profit )then
z = profit
x(1:n) = xx(1:n)
if( z==lim )return
end if
if( xx(n)/=0 )then
xx(n) = 0
ch = ch + w(n)
profit = profit - p(n)
end if
next_code_block = 5
case(5)
outer_loop: do ! BACKTRACK.
nn = ii - 1
if( nn==0 )return
middle_loop: do j = 1 , nn
kk = ii - j
if( xx(kk)==1 )then
r = ch
ch = ch + w(kk)
profit = profit - p(kk)
xx(kk) = 0
if( r<min(kk) )then
nn = kk + 1
ii = kk
! TRY TO SUBSTITUTE THE NN-TH ITEM FOR THE KK-TH.
inner_loop: do while ( z<profit + ch*p(nn)/w(nn) )
diff = w(nn) - w(kk)
if( diff<0 )then
t = r - diff
if( t>=min(nn) )then
if( z>=profit + p(nn) + t*p(nn + 1)/w(nn + 1) )exit inner_loop
ch = ch - w(nn)
profit = profit + p(nn)
xx(nn) = 1
ii = nn + 1
wsign(nn) = w(nn)
psign(nn) = p(nn)
zsign(nn) = ii
n1 = nn + 1
wsign(n1:lold) = 0
psign(n1:lold) = 0
zsign(n1:lold) = [(jtemp, jtemp = n1,lold)]
lold = nn
next_code_block = 2
cycle dispatch_loop
end if
else if( diff/=0 )then
if( diff<=r )then
if( z<profit + p(nn) )then
z = profit + p(nn)
x(1:kk) = xx(1:kk)
jj = kk + 1
x(jj:n) = 0
x(nn) = 1
if( z==lim )return
r = r - diff
kk = nn
nn = nn + 1
cycle inner_loop
end if
end if
end if
nn = nn + 1
end do inner_loop
cycle outer_loop
else
ii = kk + 1
next_code_block = 2
cycle dispatch_loop
end if
end if
end do middle_loop
exit outer_loop
end do outer_loop
exit dispatch_loop
end select
end do dispatch_loop
end subroutine mt1
!
subroutine chmt1(n , p , w , c , z , jdim)
integer , intent(in) :: jdim
integer , intent(in) :: n
integer , intent(in) , dimension(jdim) :: p
integer , intent(in) , dimension(jdim) :: w
integer , intent(in) :: c
integer , intent(out) :: z
!
! Local variable declarations
!
integer :: j
integer :: jsw
real :: r
real :: rr
!
! CHECK THE INPUT DATA.
!
if(( n<2) .or. (n>jdim - 1) )then
z = -1
return
else if( c>0 )then
jsw = 0
rr = float(p(1))/float(w(1))
do j = 1 , n
r = rr
if(( p(j)<=0 ).or.( w(j)<=0 ))then
z = -2
return
end if
jsw = jsw + w(j)
if( w(j)<=c )then
rr = float(p(j))/float(w(j))
if( rr>r )then
z = -5
return
end if
else
z = -3
return
end if
end do
if( jsw>c )return
z = -4
return
end if
z = -2
return
end subroutine chmt1
subroutine start_knapsack(n , profit , weight , capacity , result_val , members)
!
! Dummy argument declarations
!
integer , intent(in) :: n
integer , intent(inout) , dimension(n) :: profit
integer , intent(inout) , dimension(n) :: weight
integer , intent(in) :: capacity
integer , intent(inout) :: result_val
integer , intent(inout) , dimension(n) :: members
!
! Local variable declarations
integer :: bigger
integer :: jck
integer , allocatable , dimension(:) :: mini
integer , allocatable , dimension(:) :: psign
integer , allocatable , dimension(:) :: wsign
integer , allocatable , dimension(:) :: xx
integer , allocatable , dimension(:) :: zsign
!
!Designed to invoke MT1
!MT1 NEEDS 8 ARRAYS ( P , W , X , XX , MIN , PSIGN , WSIGN
! AND ZSIGN ) OF LENGTH AT LEAST N + 1 .
! MEANING OF THE INPUT PARAMETERS:
! N = NUMBER OF ITEMS;
! P(J) = PROFIT OF ITEM J (J=1,...,N);
! W(J) = WEIGHT OF ITEM J (J=1,...,N);
! C = CAPACITY OF THE KNAPSACK;
! JDIM = DIMENSION OF THE 8 ARRAYS;
! JCK = 1 IF CHECK ON THE INPUT DATA IS DESIRED,
! = 0 OTHERWISE.
!
! MEANING OF THE OUTPUT PARAMETERS:
! Z = VALUE OF THE OPTIMAL SOLUTION IF Z .GT. 0 ,
! = ERROR IN THE INPUT DATA (WHEN JCK=1) IF Z .LT. 0 : CONDI-
! TION - Z IS VIOLATED;
! X(J) = 1 IF ITEM J IS IN THE OPTIMAL SOLUTION,
! = 0 OTHERWISE.
!
! ARRAYS XX, MIN, PSIGN, WSIGN AND ZSIGN ARE DUMMY.
!
! ALL THE PARAMETERS ARE INTEGER. ON RETURN OF MT1 ALL THE INPUT
! PARAMETERS ARE UNCHANGED.
!
jck = 1 !Set parameter checking on
bigger = n + 100
!
! Allocate the dummy arrays
allocate(xx(bigger))
allocate(mini(bigger))
allocate(psign(bigger))
allocate(wsign(bigger))
allocate(zsign(bigger))
call mt1(n , profit , weight , capacity , result_val , members , bigger , jck , xx , mini , psign , wsign , zsign)
deallocate(xx)
deallocate(mini)
deallocate(psign)
deallocate(wsign)
deallocate(zsign)
end subroutine start_knapsack
end module ksack2
!
program serious_knapsack
use ksack2
integer, parameter :: list_size=22
integer:: p(list_size) ! The weights
integer::n,profit(list_size),capacity,result_val,members(size(p)),valuez,t1,t2,j
character(len=25) :: names(list_size),tempnam
real :: ratio(list_size),rats
logical :: swapped
capacity =400
members = 0
result_val = 0
n = list_size
p(1:list_size) = (/13,153, 50,15,68,27,39,23,52,11,32,24,48,73,43,42,22,07,18,009,04,30/)
profit(1:list_size) =(/35,200,160,60,45,60,40,30,10,70,30,15,10,40,70,75,80,20,12,150,50,10/)
names(1:22) =[character(len=25) ::'compass','water','sandwich','glucose','tin','banana','apple', 'cheese', &
'beer','suntan cream','camera','T-shirt','trousers','umbrella','waterproof trousers', 'waterproof overclothes', &
'note-case','sunglasses','towel','map','socks', 'book']
ratio(1:22) = float(profit(1:22))/float(p(1:22))
! The mt1 algorithm wants the data sorted downwards(large-->small) by the ration of profit/weight
! So, I implemented a quick bubble sort to order the lists
swapped = .true.
do while (swapped)
swapped = .false.
do j = 1,21
if(ratio(j).lt.ratio(j+1))then ! Swaps everywhere
swapped = .true.
t1 = p(j+1) ! Swap the weights
p(j+1) = p(j)
p(j) = t1
t2 = profit(j+1) !Swap the profits
profit(j+1) = profit(j)
profit(j) = t2
tempnam = names(j+1) ! Swap the names around
names(j+1) = names(j)
names(j) = tempnam
rats = ratio(j+1) ! Swap the ratios
ratio(j+1) = ratio(j)
ratio(j) = rats
endif
end do
end do
!
call system_clock(count=xx)
call startup(n,profit(1:22),p(1:22),capacity,result_val,members)
call system_clock(count=yy)
print*,'Total of the sack = ',result_val
capacity = 0
valuez = 0
n = 0
do i = 1,size(members)
if(members(i) /=0)then
capacity = capacity +p(i)
valuez = profit(i) + valuez
n = n+1
print*, names(i),p(i),profit(i)
endif
end do
print*,'Filled capacity = ',capacity,'Value = ',valuez!,'No items = ',n,sum(profit(1:22)),sum(p(1:22))
print*
print*,'First knapsack time = ',(yy-xx),'Milliseconds'
stop 'All done'
end program serious_knapsack
</syntaxhighlight>
{{out}}
<pre>
map 9 150
socks 4 50
suntan cream 11 70
glucose 15 60
note-case 22 80
sandwich 50 160
sunglasses 7 20
compass 13 35
banana 27 60
waterproof overclothes 42 75
waterproof trousers 43 70
water 153 200
Filled capacity = 396 Value = 1030
First knapsack time = 0 Milliseconds
</pre>
=={{header|FreeBASIC}}==
{{trans|XPL0}}
<
Dim As Integer i, A, P, V, N
Dim As Integer MejorArticulo, MejorValor = 0
Line 3,068 ⟶ 3,859:
Wend
Print "Totals:"; Spc(25); P; Tabu; V
Sleep</
{{out}}
<pre>Same as XLP0 entry.</pre>
=={{header|
Dynamic programming solution(tested with FPC 3.2.2).
<syntaxhighlight lang="pascal">
program Knapsack01;
{$mode objfpc}{$j-}
uses
Math;
type
TItem = record
Name: string;
Weight, Value: Integer;
end;
const
NUM_ITEMS = 22;
ITEMS: array[0..NUM_ITEMS-1] of TItem = (
(Name: 'map'; Weight: 9; Value: 150),
(Name: 'compass'; Weight: 13; Value: 35),
(Name: 'water'; Weight: 153; Value: 200),
(Name: 'sandwich'; Weight: 50; Value: 160),
(Name: 'glucose'; Weight: 15; Value: 60),
(Name: 'tin'; Weight: 68; Value: 45),
(Name: 'banana'; Weight: 27; Value: 60),
(Name: 'apple'; Weight: 39; Value: 40),
(Name: 'cheese'; Weight: 23; Value: 30),
(Name: 'beer'; Weight: 52; Value: 10),
(Name: 'suntan cream'; Weight: 11; Value: 70),
(Name: 'camera'; Weight: 32; Value: 30),
(Name: 'T-shirt'; Weight: 24; Value: 15),
(Name: 'trousers'; Weight: 48; Value: 10),
(Name: 'umbrella'; Weight: 73; Value: 40),
(Name: 'waterproof trousers'; Weight: 42; Value: 70),
(Name: 'waterproof overclothes'; Weight: 43; Value: 75),
(Name: 'note-case'; Weight: 22; Value: 80),
(Name: 'sunglasses'; Weight: 7; Value: 20),
(Name: 'towel'; Weight: 18; Value: 12),
(Name: 'socks'; Weight: 4; Value: 50),
(Name: 'book'; Weight: 30; Value: 10)
);
MAX_WEIGHT = 400;
var
D: array of array of Integer;
I, W, V, 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
if ITEMS[I].Weight > W then
D[I+1, W] := D[I, W]
else
D[I+1, W] := Max(D[I, W], D[I, W - ITEMS[I].Weight] + ITEMS[I].Value);
W := MAX_WEIGHT;
V := D[NUM_ITEMS, W];
MaxWeight := 0;
WriteLn('bagged:');
for I := High(ITEMS) downto 0 do
if (D[I+1, W] = V)and(D[I, W - ITEMS[I].Weight] = V - ITEMS[I].Value)then begin
WriteLn(' ', ITEMS[I].Name);
Inc(MaxWeight, ITEMS[I].Weight);
Dec(W, ITEMS[I].Weight);
Dec(V, ITEMS[I].Value);
end;
WriteLn('value = ', D[NUM_ITEMS, MAX_WEIGHT]);
WriteLn('weight = ', MaxWeight);
end.
</syntaxhighlight>
{{out}}
<pre>
bagged:
socks
sunglasses
note-case
waterproof overclothes
waterproof trousers
suntan cream
banana
glucose
sandwich
water
compass
map
value = 1030
weight = 396
</pre>
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">window 1, @"Knapsack Problem", (0,0,480,270)
_maxWeight = 400
void local fn FillKnapsack
long totalWeight = 0, totalValue = 0, itemWeight, unusedWeight
CFDictionaryRef item, extraItem = NULL
SortDescriptorRef sd
CFMutableArrayRef packedItems
CFArrayRef items = @[
@{@"item":@"map", @"weight":@9, @"value":@150},
@{@"item":@"compass", @"weight":@13, @"value":@35 },
@{@"item":@"water", @"weight":@153, @"value":@200},
@{@"item":@"sandwich", @"weight":@50, @"value":@160},
@{@"item":@"glucose", @"weight":@15, @"value":@60 },
@{@"item":@"tin", @"weight":@68, @"value":@45 },
@{@"item":@"banana", @"weight":@27, @"value":@60 },
@{@"item":@"apple", @"weight":@39, @"value":@40 },
@{@"item":@"cheese", @"weight":@23, @"value":@30 },
@{@"item":@"beer", @"weight":@52, @"value":@10 },
@{@"item":@"suntan cream", @"weight":@11, @"value":@70 },
@{@"item":@"camera", @"weight":@32, @"value":@30 },
@{@"item":@"T-shirt", @"weight":@24, @"value":@15 },
@{@"item":@"trousers", @"weight":@48, @"value":@10 },
@{@"item":@"umbrella", @"weight":@73, @"value":@40 },
@{@"item":@"waterproof trousers", @"weight":@42, @"value":@70 },
@{@"item":@"waterproof overclothes", @"weight":@43, @"value":@75 },
@{@"item":@"note-case", @"weight":@22, @"value":@80 },
@{@"item":@"sunglasses", @"weight":@7, @"value":@20 },
@{@"item":@"towel", @"weight":@18, @"value":@12 },
@{@"item":@"socks", @"weight":@4, @"value":@50 },
@{@"item":@"book", @"weight":@30, @"value":@10 }
]
sd = fn SortDescriptorWithKey( @"value", NO )
items = fn ArraySortedArrayUsingDescriptors( items, @[sd] )
packedItems = fn MutableArrayWithCapacity(0)
for item in items
itemWeight = fn NumberIntegerValue(item[@"weight"])
if ( totalWeight + itemWeight <= _maxWeight )
MutableArrayAddObject( packedItems, item )
totalWeight += itemWeight
totalValue += fn NumberIntegerValue(item[@"value"])
end if
next
text @"Menlo-Bold",,, fn ColorWithRGB(1.0,0.0,1.0,0.25),, 170
print @"Item",@"Weight",@"Value"
text @"Menlo",,, fn ColorClear
for item in packedItems
printf @"%@\t%6ld\t%5ld",item[@"item"],fn NumberIntegerValue(item[@"weight"]),fn NumberIntegerValue(item[@"value"])
next
text ,,, fn ColorWithRGB(1.0,0.0,1.0,0.25)
printf @"knapsack\t%6ld\t%5ld",totalWeight,totalValue
text
print
unusedWeight = _maxWeight - totalWeight
for item in items
if ( fn NumberIntegerValue(item[@"weight"]) <= unusedWeight )
extraItem = item : break
end if
next
if ( extraItem ) then printf @"There's just enough room for extra %@!", extraItem[@"item"]
end fn
fn FillKnapsack
HandleEvents</syntaxhighlight>
{{output}}
<pre>
Item Weight Value
water 153 200
sandwich 50 160
map 9 150
note-case 22 80
waterproof overclothes 43 75
suntan cream 11 70
waterproof trousers 42 70
glucose 15 60
banana 27 60
socks 4 50
compass 13 35
sunglasses 7 20
knapsack 396 1030
There's just enough room for extra socks!
</pre>
=={{header|Go}}==
From WP, "0-1 knapsack problem" under [http://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_Programming_Algorithm|Solving The Knapsack Problem], although the solution here simply follows the recursive defintion and doesn't even use the array optimization.
<
import "fmt"
Line 3,341 ⟶ 4,105:
}
return i0, w0, v0
}</
{{out}}
<pre>
Line 3,351 ⟶ 4,115:
Data for which a greedy algorithm might give an incorrect result:
<syntaxhighlight lang="go">
var wants = []item{
{"sunscreen", 15, 2},
Line 3,359 ⟶ 4,123:
const maxWt = 40
</syntaxhighlight>
{{out}}
<pre>
Line 3,369 ⟶ 4,133:
=={{header|Groovy}}==
Solution #1: brute force
<
def totalValue = { list -> list*.value.sum() }
Line 3,377 ⟶ 4,141:
350 < w && w < 401
}.max(totalValue)
}</
Solution #2: dynamic programming
<
def n = possibleItems.size()
def m = (0..n).collect{ i -> (0..400).collect{ w -> []} }
Line 3,389 ⟶ 4,153:
}
m[n][400]
}</
Test:
<
[name:"map", weight:9, value:150],
[name:"compass", weight:13, value:35],
Line 3,427 ⟶ 4,191:
printf (" item: %-25s weight:%4d value:%4d\n", it.name, it.weight, it.value)
}
}</
{{out}}
<pre>Elapsed Time: 132.267 s
Line 3,465 ⟶ 4,229:
=={{header|Haskell}}==
Brute force:
<
("glucose",15,60), ("tin",68,45), ("banana",27,60), ("apple",39,40),
("cheese",23,30), ("beer",52,10), ("cream",11,70), ("camera",32,30),
Line 3,481 ⟶ 4,245:
putStr "Total value: "; print value
mapM_ print items
where (value, items) = maximum $ combs inv 400</
{{out}}
<pre>
Line 3,499 ⟶ 4,263:
</pre>
Much faster brute force solution that computes the maximum before prepending, saving most of the prepends:
<
("glucose",15,60), ("tin",68,45), ("banana",27,60), ("apple",39,40),
("cheese",23,30), ("beer",52,10), ("cream",11,70), ("camera",32,30),
Line 3,513 ⟶ 4,277:
skipthis = combs rest cap
main = do print $ combs inv 400</
{{out}}
<pre>(1030,[("map",9,150),("compass",13,35),("water",153,200),("sandwich",50,160),("glucose",15,60),("banana",27,60),("cream",11,70),("trousers",42,70),("overclothes",43,75),("notecase",22,80),("sunglasses",7,20),("socks",4,50)])</pre>
Dynamic programming with a list for caching (this can be adapted to bounded problem easily):
<
("glucose",15,60), ("tin",68,45), ("banana",27,60), ("apple",39,40),
("cheese",23,30), ("beer",52,10), ("cream",11,70), ("camera",32,30),
Line 3,530 ⟶ 4,294:
(left,right) = splitAt w list
main = print $ (knapsack inv) !! 400</
{{out}}
(1030,["map","compass","water","sandwich","glucose","banana","cream","waterproof trousers","overclothes","notecase","sunglasses","socks"])
Line 3,536 ⟶ 4,300:
=={{header|Icon}} and {{header|Unicon}}==
Translation from Wikipedia pseudo-code. Memoization can be enabled with a command line argument that causes the procedure definitions to be swapped which effectively hooks the procedure.
<
global wants # items wanted for knapsack
Line 3,611 ⟶ 4,375:
packing(["socks"], 4, 50),
packing(["book"], 30, 10) ]
end</
{{libheader|Icon Programming Library}}
[http://www.cs.arizona.edu/icon/library/src/procs/printf.icn printf.icn provides printf]
Line 3,625 ⟶ 4,389:
=={{header|J}}==
Static solution:
<
'map'; 9 150
'compass'; 13 35
Line 3,652 ⟶ 4,416:
X=: +/ .*"1
plausible=: (] (] #~ 400 >: X) #:@i.@(2&^)@#)@:({."1)
best=: (plausible ([ {~ [ (i. >./)@:X {:"1@]) ]) values</
Illustration of answer:
<
396 1030
best#names
Line 3,668 ⟶ 4,432:
notecase
sunglasses
socks </
'''Alternative test case'''
<
'sunscreen'; 15 2
'GPS'; 25 2
Line 3,680 ⟶ 4,444:
X=: +/ .*"1
plausible=: (] (] #~ 40 >: X) #:@i.@(2&^)@#)@:({."1)
best=: (plausible ([ {~ [ (i. >./)@:X {:"1@]) ]) values</
Illustration:
<
40 4
best#names
sunscreen
GPS </
=={{header|Java}}==
General dynamic solution after [[wp:Knapsack_problem#0-1_knapsack_problem|wikipedia]].
<
import hu.pj.alg.ZeroOneKnapsack;
Line 3,775 ⟶ 4,539:
}
} // class</
<
import hu.pj.obj.Item;
Line 3,929 ⟶ 4,693:
}
} // class</
<
public class Item {
Line 4,000 ⟶ 4,764:
public int getBounding() {return bounding;}
} // class</
{{out}}
<pre>
Line 4,024 ⟶ 4,788:
=={{header|JavaScript}}==
Also available at [https://gist.github.com/truher/4715551|this gist].
<
/*
* 0-1 knapsack solution, recursive, memoized, approximate.
Line 4,225 ⟶ 4,989:
12
]);
});</
=={{header|JavaScript}}==
Knapsack 0-1 JavaScript Russian Binary ciphers
Russian Knapsack 0-1 synthesizes all ciphers from 0 & 1 adding left +1 register and 0 remain on left in cipher
Copy and save as knapsackda.htm
<syntaxhighlight lang="javascript">
<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<title>KNAPSACK 22 JavaScript</title> </head> <body> <noscript>Vkluch JS</noscript>
https://jdoodle.com/h/2Ut
rextester.com/BQYV50962
<script>
var n=22; G=400; a = Math.pow(2,n+1); // KNAPSACKj.js
var dec, i, h, k, max, m, s;
var L=[n], C=[n], j=[n], q=[a], d=[a]; e=[a];
document.write("<br><br># Kol Cena<br>")
document.write("# Amo Price<br><br>")
L=[ 9,13,153,50,15,68,27,39,23,52,11,32,24,48,73,42,43,22,7,18,4,30 ]
C=[ 150,35,200,160,60,45,60,40,30,10,70,30,15,10,40,70,75,80,20,12,50,10 ]
for (i=0; i<n; i++)
{ // L[i]=1+Math.floor(Math.random()*3)
// C[i]=10+Math.floor(Math.random()*9);
j[i]=0;
document.write( (i+1) +" "+ L[i] +" "+ C[i] +"<br>")
}
for (i=0; i<a; i++) { q[i]=0; d[i]=0;}
document.write("<br>")
document.write("Mx Kol St-st Schifr<br>")
document.write("Mx Amo Price Cipher<br>")
for (h = a-1; h>(a-1)/2; h--)
{ dec=h; e[h]=""
while (dec > 0)
{ s = Math.floor(dec % 2);
e[h] = s + e[h]; dec = Math.floor(dec/2);
}
if (e[h] == "") {e[h] = "0";}
e[h]= e[h].substr(1, e[h].length-1);
for (k=0; k<n; k++)
{ j[k] = Number(e[h].substr(k,1));
q[h]=q[h]+j[k]*C[k];
d[h]=d[h]+L[k]*j[k];
}
// if (d[h] <= G)
// document.write("<br>"+ G +" "+ d[h] +" "+ q[h] +" "+ e[h])
} document.write("<br>")
max=0; m=1;
for (i=0; i<a; i++)
{ if (d[i]<=G && q[i]>max){ max=q[i]; m=i;}
}
document.write("<br>"+ d[m] +" "+ q[m] +" "+ e[m] +"<br><br>")
document.write("Mx St-st Schifr<br>")
document.write("Mx Price Cipher<br><br>")
</script>
</body> </html>
</syntaxhighlight>
=={{header|jq}}==
Line 4,235 ⟶ 5,080:
corresponding to no items). Here, m[i,W] is set to [V, ary]
where ary is an array of the names of the accepted items.
<
# Because of the way addition is defined on null and because of the
# way setpath works, there is no need to initialize the matrix m in
Line 4,259 ⟶ 5,104:
.[$i][$j] = .[$i-1][$j]
end))
| .[$n][W];</
'''Example''':
<
{name: "map", "weight": 9, "value": 150},
{name: "compass", "weight": 13, "value": 35},
Line 4,286 ⟶ 5,131:
];
objects | dynamic_knapsack(400)[]</
{{out}}
<
1030
["map","compass","water","sandwich","glucose","banana","suntancream","waterproof trousers","waterproof overclothes","note-case","sunglasses","socks"]</
=={{header|Julia}}==
Line 4,298 ⟶ 5,143:
'''Type and Functions''':
<
item::String
weight::T
Line 4,314 ⟶ 5,159:
sol = mixintprog(-v, w', '<', capacity, :Bin, 0, 1, CbcSolver())
gear[sol.sol .≈ 1]
end</
'''Main''':
<
KPDSupply("compass", 13, 35),
KPDSupply("water", 153, 200),
Line 4,343 ⟶ 5,188:
println("The hicker should pack: \n - ", join(pack, "\n - "))
println("\nPacked weight: ", mapreduce(x -> x.weight, +, pack), " kg")
println("Packed value: ", mapreduce(x -> x.value, +, pack), " €")</
{{out}}
Line 4,365 ⟶ 5,210:
=={{header|Kotlin}}==
{{trans|Go}}
<
data class Item(val name: String, val weight: Int, val value: Int)
Line 4,418 ⟶ 5,263:
println("---------------------- ------ -----")
println("Total ${chosenItems.size} Items Chosen $totalWeight $totalValue")
}</
{{out}}
Line 4,442 ⟶ 5,287:
=={{header|LSL}}==
To test it yourself, rez a box on the ground, add the following as a New Script, create a notecard named "Knapsack_Problem_0_1_Data.txt" with the data shown below.
<
integer iMAX_WEIGHT = 400;
integer iSTRIDE = 4;
Line 4,491 ⟶ 5,336:
}
}
}</
Notecard:
<pre>map, 9, 150
Line 4,534 ⟶ 5,379:
=={{Header|Lua}}==
This version is adapted from the Clojure version.
<
{"map", 9, 150},
{"compass", 13, 35},
Line 4,619 ⟶ 5,464:
for k,v in pairs(memo) do count = count + 1 end
printf("\n(memo count: %d; mm call count: %d)", count, mm_calls)
</syntaxhighlight>
{{out}}
Line 4,629 ⟶ 5,474:
</pre>
=={{header|Maple}}==
<
vals := [150,35,200,160,60,45,60,40,30,10,70,30,15,10,40,70,75,80,20,12,50,10]:
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 4,657 ⟶ 5,502:
end if:
end do:
printf("Total Weight is %d\n", count):</
{{Out}}
<pre>Total Value is 1030
Line 4,676 ⟶ 5,521:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
Used the
<
Position[LinearProgramming[-#[[;; , 3]], -{#[[;; , 2]]}, -{400},
{0, 1} & /@ #, Integers], 1], 1]] &@
Line 4,700 ⟶ 5,545:
{"towel", 18, 12},
{"socks", 4, 50},
{"book", 30, 10}}</
{{Out}}
<pre>{"map", "compass", "water", "sandwich", "glucose", "banana", "suntan cream", "waterproof trousers", "waterproof overclothes", "note-case", "sunglasses", "socks"}</pre>
=={{header|Mathprog}}==
<
This model finds the integer optimal packing of a knapsack
Line 4,750 ⟶ 5,595:
;
end;</
The solution may be found at [[Knapsack problem/0-1/Mathprog]].
Activity=1 means take, Activity=0 means don't take.
=={{header|MAXScript}}==
<syntaxhighlight lang="maxscript">
global globalItems = #()
global usedMass = 0
Line 4,819 ⟶ 5,664:
)
format "Total mass: %, Total Value: %\n" usedMass totalValue
</syntaxhighlight>
{{out}}
<syntaxhighlight lang="maxscript">
Item name: water, weight: 153, value:200
Item name: sandwich, weight: 50, value:160
Line 4,837 ⟶ 5,682:
Total mass: 396, Total Value: 1030
OK
</syntaxhighlight>
=={{header|MiniZinc}}==
<syntaxhighlight lang="minizinc">
%Knapsack 0/1. Nigel Galloway: October 5th., 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 4,852 ⟶ 5,697:
solve maximize wValue;
output["Take "++show(take)++"\nTotal Weight=\(wTaken) Total Value=\(wValue)"]
</syntaxhighlight>
{{out}}
<pre>
Line 4,864 ⟶ 5,709:
:– use a cache for memoization.
<syntaxhighlight lang="nim">
# Knapsack. Recursive algorithm.
Line 4,947 ⟶ 5,792:
echo "Total weight: ", weight
echo "Total value: ", value
</syntaxhighlight>
{{out}}
Line 4,971 ⟶ 5,816:
=={{header|OCaml}}==
A brute force solution:
<
"map", 9, 150;
"compass", 13, 35;
Line 5,011 ⟶ 5,856:
(List.hd poss) (List.tl poss) in
List.iter (fun (name,_,_) -> print_endline name) res;
;;</
=={{header|Oz}}==
Using constraint programming.
<
%% maps items to pairs of Weight(hectogram) and Value
Problem = knapsack('map':9#150
Line 5,078 ⟶ 5,923:
{System.printInfo "\n"}
{System.showInfo "total value: "#{Value Best}}
{System.showInfo "total weight: "#{Weight Best}}</
{{out}}
<pre>
Line 5,102 ⟶ 5,947:
=={{header|Pascal}}==
Uses a stringlist to store the items. I used the algorithm given on Wikipedia (Knapsack problem) to find the maximum value. It is written in pseudocode that translates very easily to Pascal.
<
program project1;
uses
Line 5,109 ⟶ 5,954:
const
MaxWeight = 400;
N =
type
Line 5,124 ⟶ 5,969:
var
M:TMaxArray;
MaxValue, WeightLeft, i, j
S,KnapSack:TStringList;
L:string;
Line 5,131 ⟶ 5,976:
begin
//Put all the items into an array called List
L:=
'map ,9,150,compass,13,35,water,153,200,sandwich,50,160,glucose,15,60,tin,68,45,banana,27,60,apple,39,40,' +
'cheese,23,30,beer,52,10,suntancreme,11,70,camera,32,30,T-shirt,24,15,trousers,48,40,umbrella,73,40,' +
'waterprooftrousers,42,70,waterproofoverclothes,43,75,notecase,22,80,sunglasses,7,20,towel,18,12,' +
'socks,4,50,book,30,10';
S:=TStringList.create;
S.Commatext:=L;
Line 5,145 ⟶ 5,994:
//and recording the value at that point
for j := 0 to MaxWeight do
M[0, j] := 0;
for i := 1 to N do
Line 5,155 ⟶ 6,004:
//get the highest total value by testing every value in table M
MaxValue := 0;
for i:=1 to N do
for j:= 0 to MaxWeight do
Line 5,172 ⟶ 6,022:
MaxValue := MaxValue - List[i].Value;
WeightLeft := WeightLeft - List[i].Weight;
end;
//Show the items in the knapsack
Line 5,186 ⟶ 6,036:
readln;
end.
</syntaxhighlight>
Output
Line 5,211 ⟶ 6,061:
=={{header|Perl}}==
The dynamic programming solution from Wikipedia.
<
map 9 150
compass 13 35
Line 5,269 ⟶ 6,119:
my $solution = optimal($#name, $max_weight);
print "$solution->[0]: @{$solution->[1]}\n";</
{{out}}
<pre>1030: map compass water sandwich glucose banana suntancream waterproof trousers waterproof overclothes note-case sunglasses socks</pre>
Line 5,275 ⟶ 6,125:
=={{header|Phix}}==
Trivial simplification of the [[Knapsack_problem/Bounded#Phix|Knapsack/Bounded]] solution. By careful ordering we can ensure we find the optimal solution first (see terminate flag).
<!--<
<span style="color: #000080;font-style:italic;">-- demo\rosetta\knapsack0.exw</span>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
Line 5,348 ⟶ 6,198:
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</
{{out}}
<pre>
Line 5,371 ⟶ 6,221:
=={{header|PHP}}==
<
# 0-1 Knapsack Problem Solve with memoization optimize and index returns
# $w = weight of item
Line 5,470 ⟶ 6,320:
}
echo "<tr><td align=right><b>Totals</b></td><td>$totalVal</td><td>$totalWt</td></tr>";
echo "</table><hr>";</
{{out}}
<div class="solutionoutput">
Line 5,476 ⟶ 6,326:
</div>
Minimal PHP Algorithm for totals only translated from Python version as discussed in the YouTube posted video at: http://www.youtube.com/watch?v=ZKBUu_ahSR4
<
# 0-1 Knapsack Problem Solve
# $w = weight of item
Line 5,569 ⟶ 6,419:
$m3 = knapSolve($w3, $v3, sizeof($v3) -1, 54 );
print_r($w3); echo "<br>";
echo "<b>Max: $m3</b> ($numcalls calls)<br><br>";</
{{out}}
<pre>
Line 5,580 ⟶ 6,430:
=={{header|Picat}}==
<
go =>
Line 5,648 ⟶ 6,498:
["socks", 4, 50],
["book", 30, 10]],
MaxTotalWeight = 400.</
{{out}}
Line 5,670 ⟶ 6,520:
=={{header|PicoLisp}}==
<
("map" 9 150) ("compass" 13 35)
("water" 153 200) ("sandwich" 50 160)
Line 5,696 ⟶ 6,546:
(for I K
(apply tab I (3 -24 6 6) NIL) )
(tab (27 6 6) NIL (sum cadr K) (sum caddr K)) )</
{{out}}
<pre>
Line 5,718 ⟶ 6,568:
===Using the clpfd library===
{{libheader|clpfd}}
<
knapsack :-
Line 5,787 ⟶ 6,637:
sformat(W3, A3, [V]),
format('~w~w~w~n', [W1,W2,W3]),
print_results(A1, A2, A3, T, TR, WM, VM).</
{{out}}
<pre>
Line 5,808 ⟶ 6,658:
{{libheader|simplex}}
Library written by <b>Markus Triska</b>. The problem is solved in about 3 seconds.
<
knapsack :-
Line 5,885 ⟶ 6,735:
W2 is W1 + W,
V2 is V1 + V),
print_results(S, A1, A2, A3, T, TN, W2, V2).</
=={{header|PureBasic}}==
Solution uses memoization.
<
name.s
weight.i ;units are dekagrams (dag)
Line 6,004 ⟶ 6,854:
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()
CloseConsole()
EndIf </
{{out}}
<pre>
Line 6,034 ⟶ 6,884:
Program write results to qb64 directory
<
N=7: L=5: a = 2^(N+1): Randomize Timer 'knapsack.bas DANILIN
Dim L(N), C(N), j(N), q(a), q$(a), d(a)
Line 6,057 ⟶ 6,907:
If d(i)<=L Then If q(i) > max Then max=q(i): m=i
Next
Print #1,: Print #1, d(m), q(m), q$(m): End</
Main thing is very brief and clear to even all<br/><br/>
Line 6,085 ⟶ 6,935:
=={{header|Python}}==
===Brute force algorithm===
<
def anycomb(items):
Line 6,115 ⟶ 6,965:
'\n '.join(sorted(item for item,_,_ in bagged)))
val, wt = totalvalue(bagged)
print("for a total value of %i and a total weight of %i" % (val, -wt))</
{{out}}
<pre>
Line 6,134 ⟶ 6,984:
</pre>
=== Dynamic programming solution ===
<
xrange
except:
Line 6,186 ⟶ 7,036:
'\n '.join(sorted(item for item,_,_ in bagged)))
val, wt = totalvalue(bagged)
print("for a total value of %i and a total weight of %i" % (val, -wt))</
===Recursive dynamic programming algorithm===
<
return sum([x[2] for x in items]) if sum([x[1] for x in items]) <= max_weight else 0
Line 6,223 ⟶ 7,073:
print x[0]
print "value:", total_value(solution, max_weight)
print "weight:", sum([x[1] for x in solution])</
Line 6,235 ⟶ 7,085:
Random values origin are automatically assigned create integral of quantity and quality
<
L=[];C=[];e=[];j=[];q=[];s=[] # rextester.com/BCKP19591
d=[];L=[1]*n;C=[1]*n;e=[1]*a
Line 6,264 ⟶ 7,114:
if d[i]<=G and q[i]>max:
max=q[i]; m=i
print (d[m], q[m], e[m])</
{{out}}
<pre># Mass Cost
Line 6,284 ⟶ 7,134:
=={{header|R}}==
<syntaxhighlight lang="r">
Full_Data<-structure(list(item = c("map", "compass", "water", "sandwich",
"glucose", "tin", "banana", "apple", "cheese", "beer", "suntan_cream",
Line 6,364 ⟶ 7,214:
print_output(Full_Data, 400)
</syntaxhighlight>
{{out}}
<syntaxhighlight lang="text">
[1] "You must carry: socks"
[2] "You must carry: sunglasses"
Line 6,380 ⟶ 7,230:
[11] "You must carry: compass"
[12] "You must carry: map"
</syntaxhighlight>
=={{header|Racket}}==
<
#lang racket
; An ITEM a list of three elements:
Line 6,440 ⟶ 7,290:
(trousers 42 70) (overclothes 43 75) (notecase 22 80)
(glasses 7 20) (towel 18 12) (socks 4 50) (book 30 10)))
</syntaxhighlight>
{{out}}
<
'(1030 396 (map compass water sandwich glucose banana cream trousers overclothes notecase glasses socks))
</syntaxhighlight>
Brute Force and Memoized Recursive Alternate
<
#lang racket
Line 6,480 ⟶ 7,330:
'value: (pack-value pack)
'items: (map car pack))))
</syntaxhighlight>
Brute Force
<
(define (show-brute)
Line 6,500 ⟶ 7,350:
(show-brute); takes around five seconds on my machine
</syntaxhighlight>
Recursive Alternate
<
(define (show-memoized)
Line 6,527 ⟶ 7,377:
(show-memoized)
</syntaxhighlight>
{{out}}
<
(weight: 396 value: 1030 items: (map compass water sandwich glucose banana cream trousers overclothes notecase glasses socks))
</syntaxhighlight>
=={{header|Raku}}==
Line 6,538 ⟶ 7,388:
==== Brute force ====
{{works with|Rakudo|2017.01}}
<syntaxhighlight lang="raku"
multi sub pokem ([], $, $v = 0) { $v }
Line 6,582 ⟶ 7,432:
my ($value, @result) = pokem @table, $MAX_WEIGHT;
say "Value = $value\nTourist put in the bag:\n " ~ @result;</
{{out}}
<pre>Value = 1030
Line 6,591 ⟶ 7,441:
Much faster than the previous example.
{{trans|Perl}}
<syntaxhighlight lang="raku"
map 9 150
compass 13 35
Line 6,650 ⟶ 7,500:
my @solution = optimal(@name.end, $sum);
put "@solution[0]: ", @solution[1].sort.join(', ');</
{{out}}
<pre>1030: banana, compass, glucose, map, note-case, sandwich, socks, sunglasses, suntancream, water, waterproof overclothes, waterproof trousers
Line 6,661 ⟶ 7,511:
The term ''allowable items'' refers to all items that are of allowable weight (those that weigh within the weight criteria). An half metric─ton anvil was added to the list to show how overweight items are pruned from the list of items.
<
maxWeight=400 /*the maximum weight for the knapsack. */
say 'maximum weight allowed for a knapsack:' commas(maxWeight); say
Line 6,762 ⟶ 7,612:
end /*k*/
end /*j*/ /* [↑] sort choices by decreasing wt. */
obj=j-1; return /*decrement J for the DO loop index*/</
{{out|output|text= when using the default input:}}
<pre>
Line 6,819 ⟶ 7,669:
=={{header|Ruby}}==
=== Brute force ===
<
potential_items = [
KnapsackItem['map', 9, 150], KnapsackItem['compass', 13, 35],
Line 6,861 ⟶ 7,711:
puts "weight: #{wt}"
puts "items: #{items.join(',')}"
end</
{{out}}
Line 6,872 ⟶ 7,722:
=== Dynamic Programming ===
Translated from http://sites.google.com/site/mikescoderama/Home/0-1-knapsack-problem-in-p
<
def dynamic_programming_knapsack(items, max_weight)
Line 6,934 ⟶ 7,784:
puts "total weight: #{weight}"
puts "total value: #{value}"
end</
{{out}}
<pre style='width: full; overflow: scroll'>
Line 6,946 ⟶ 7,796:
=={{header|Rust}}==
Dynamic Programming solution.
<
struct Item {
Line 7,018 ⟶ 7,868:
println!("Total weight: {}", items.iter().map(|w| w.weight).sum::<usize>());
println!("Total value: {}", items.iter().map(|w| w.value).sum::<usize>());
}</
{{out}}
<pre>map
Line 7,038 ⟶ 7,888:
Use MILP solver in SAS/OR:
<
data mydata;
input item $1-23 weight value;
Line 7,086 ⟶ 7,936:
print TotalValue;
print {i in ITEMS: NumSelected[i].sol > 0.5} NumSelected;
quit;</
Output:
Line 7,110 ⟶ 7,960:
=={{header|Scala}}==
{{works with|Scala|2.9.2}}
<
case class Item(name: String, weight: Int, value: Int)
Line 7,208 ⟶ 8,058:
println(" elapsed time: "+t+" sec"+"\n")
}
}</
{{out}}
<pre>packing list of items (brute force):
Line 7,250 ⟶ 8,100:
=={{header|Sidef}}==
{{trans|Perl}}
<
map, 9, 150
compass, 13, 35
Line 7,319 ⟶ 8,169:
var sol = optimal(items.end, max_weight)
say "#{sol[0]}: #{sol[1]}"</
{{out}}
<pre>
Line 7,329 ⟶ 8,179:
Displays the top 5 solutions and runs in about 39 seconds.
<syntaxhighlight lang="sql">
WITH KnapsackItems (item, [weight], value) AS
(
Line 7,376 ⟶ 8,226:
GO
DROP TABLE #KnapsackItems;
</syntaxhighlight>
{{out}}
<pre>
Line 7,393 ⟶ 8,243:
=== Dynamic Programming ===
<
var name: String
var weight: Int
Line 7,452 ⟶ 8,302:
let (tValue, tWeight) = kept.reduce((0, 0), { ($0.0 + $1.value, $0.1 + $1.weight) })
print("For a total value of \(tValue) and a total weight of \(tWeight)")</
{{out}}
Line 7,473 ⟶ 8,323:
=={{header|Tcl}}==
As the saying goes, “when in doubt, try brute force”. Since there's only 22 items we can simply iterate over all possible choices.
<
set items {
{map 9 150}
Line 7,547 ⟶ 8,397:
# Pretty-print the results
puts "Best filling has weight of [expr {[weight $best]/100.0}]kg and score [value $best]"
puts "Best items:\n\t[join [lsort [names $best]] \n\t]"</
{{out}}
<pre>
Line 7,568 ⟶ 8,418:
=={{header|Ursala}}==
This solution follows a very similar approach to the one used in [[Knapsack problem/Bounded#Ursala]], which is to treat it as a mixed integer programming problem and solve it using an off-the-shelf library ([http://lpsolve.sourceforge.net lpsolve]).
<
#import nat
#import flo
Line 7,611 ⟶ 8,461:
#show+
main = ~&tnS solution system items</
Binary valued variables are a more specific constraint than the general mixed integer programming problem, but can be accommodated as shown using the <code>binaries</code> field in the <code>linear_system</code> specification. The additional <code>slack</code> variable is specified as continuous and non-negative with no cost or benefit so as to make the constraint equation solvable without affecting the solution.
{{out}}
Line 7,630 ⟶ 8,480:
=={{header|VBA}}==
<
Option Explicit
Const maxWeight = 400
Line 7,687 ⟶ 8,537:
Call ChoiceBin(n + 1, ss)
End If
End Sub 'ChoiceBin</
{{out}}
<pre>
Line 7,707 ⟶ 8,557:
=={{header|VBScript}}==
Non recurvive unfolded force version. Created by an other script. It runs 13 times faster than the recursive one.
<
dim w(22),v(22),m(22)
data=array( "map", 9, 150, "compass", 13, 35, "water", 153, 200, _
Line 7,920 ⟶ 8,770:
if l(i)=1 then wlist=wlist&vbCrlf&data((i-1)*3)
next
Msgbox mid(wlist,3)&vbCrlf&vbCrlf&"weight="&xw&vbCrlf&"value="&xv,,"Knapsack - nn="&nn</
{{out}}
<pre>
Line 7,942 ⟶ 8,792:
=={{header|Visual Basic}}==
{{works with|Visual Basic|VB6 Standard}}
<
Option Explicit
Const maxWeight = 400
Line 8,009 ⟶ 8,859:
Call ChoiceBin(n + 1, ss)
End If
End Sub 'ChoiceBin</
{{out}}
<pre>
Line 8,029 ⟶ 8,879:
=={{header|Visual Basic .NET}}==
{{works with|Visual Basic .NET|2013}}
<
Public Class KnapsackBin
Const knam = 0, kwei = 1, kval = 2
Line 8,112 ⟶ 8,962:
End Class 'KnapsackBin
</syntaxhighlight>
{{out}}
<pre>
Line 8,132 ⟶ 8,982:
</pre>
=={{header|V (Vlang)}}==
{{trans|go}}
<
name string
w int
Line 8,188 ⟶ 9,038:
}
return i0, w0, v0
}</
{{out}}
<pre>
Line 8,200 ⟶ 9,050:
{{libheader|Wren-fmt}}
Based on the Go example, though modified to give output in tabular form.
<
var wants = [
Line 8,259 ⟶ 9,109:
}
System.print(" --- ----")
Fmt.print("totals $3d $4d", tw, tv)</
{{out}}
Line 8,284 ⟶ 9,134:
=={{header|XPL0}}==
<
int Item, Items, Weights, Values,
Line 8,340 ⟶ 9,190:
IntOut(0, W); ChOut(0, Tab);
IntOut(0, V); CrLf(0);
]</
{{out}}
Line 8,361 ⟶ 9,211:
=={{header|zkl}}==
{{trans|Haskell}}{{trans|D}}
<
w,left,right:=it[1],pairs[0,w],pairs[w,*];
left.extend(right.zipWith(
fcn([(t1,_)]a,[(t2,_)]b){ t1>t2 and a or b },
pairs.apply('wrap([(tot,names)]){ T(tot + it[2], names + it[0]) })))
}//--> new list of pairs</
<
T("beer", 52, 10),T("book", 30,10),T("camera", 32, 30),
T("cheese", 23, 30),T("compass", 13,35),T("glucose", 15, 60),
Line 8,379 ⟶ 9,229:
(MAX_WEIGHT).pump(List,T(0,T).copy))[-1]; // nearest to max weight
weight:=items.apply('wrap(it){ knapsack[1].holds(it[0]) and it[1] }).sum(0);
knapsack.println(weight);</
{{out}}
<pre>
| |||