Knapsack problem/Bounded: Difference between revisions

Line 82:

<~~lang~~ 11l>V items = [

<syntaxhighlight lang="11l">V items = [

‘sandwich’ = (50, 60, 2),

‘map’ = (9, 150, 1),

Line 142:

w += items[name][0] * cnt

print(‘Total weight: ’w‘ Value: ’v)</~~lang~~>

print(‘Total weight: ’w‘ Value: ’v)</syntaxhighlight>

Line 162:

=={{header|AutoHotkey}}==

iterative dynamic programming solution

<~~lang~~ ~~AutoHotkey~~>Item = map,compass,water,sandwich,glucose,tin,banana,apple,cheese,beer,suntan cream

<syntaxhighlight lang="autohotkey">Item = map,compass,water,sandwich,glucose,tin,banana,apple,cheese,beer,suntan cream

,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</~~lang~~>

MsgBox % "Value = " m%N%_%W% "`nWeight = " s "`n`n" t</syntaxhighlight>

=={{header|Bracmat}}==

<~~lang~~ bracmat>(knapsack=

<syntaxhighlight lang="bracmat">(knapsack=

( things

= (map.9.150.1)

Line 274:

);

!knapsack;</~~lang~~>

!knapsack;</syntaxhighlight>

<pre> 1010

Line 291:

=={{header|C}}==

<~~lang~~ C>#include <stdio.h>

<syntaxhighlight lang="c">#include <stdio.h>

#include <stdlib.h>

Line 375:

return 0;

}

</syntaxhighlight>

</lang>

Line 393:

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

Similar to Knapsack/0-1.

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

<syntaxhighlight lang="csharp">using System; // 4790@3.6

class program

{

Line 466:

items = pItems;

}

}</~~lang~~>

}</syntaxhighlight>

=={{header|C++}}==

C++ DP solution. Initially taken from C but than fixed and refactored.

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)

<~~lang~~ cpp>#include <iostream>

<syntaxhighlight lang="cpp">#include <iostream>

#include <vector>

#include <algorithm>

Line 706:

cout << "Weight: " << solution.w << " Value: " << solution.v << endl;

return 0;

}</~~lang~~>

}</syntaxhighlight>

=={{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]

<~~lang~~ lisp>(ns knapsack

<syntaxhighlight lang="lisp">(ns knapsack

(:gen-class))

Line 771:

(println "Total value:" value)

(println "Total weight:" (reduce + (map (comp :weight items) indexes))))

</syntaxhighlight>

</lang>

<pre>

Line 791:

=={{header|Common Lisp}}==

<~~lang~~ lisp>;;; memoize

<syntaxhighlight lang="lisp">;;; memoize

(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))))</~~lang~~>

(glasses 7 20 1) (towel 18 12 2) (socks 4 50 1) (book 30 10 2))))</syntaxhighlight>

=={{header|Crystal}}==

==== Branch and Bound solution ====

<~~lang~~ ~~Ruby~~>record Item, name : String, weight : Int32, value : Int32, count : Int32

<syntaxhighlight lang="ruby">record Item, name : String, weight : Int32, value : Int32, count : Int32

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}"</~~lang~~>

puts "checked nodes: #{solver.checked_nodes}"</syntaxhighlight>

<pre>optimal choice: map, socks, suntan cream, 2x glucose, note-case, sunglasses, compass, 3x banana, waterproof overclothes, water, cheese

Line 914:

==== Dynamic programming solution ====

<~~lang~~ ~~Ruby~~># Item struct to represent each item in the problem

<syntaxhighlight lang="ruby"># Item struct to represent each item in the problem

record Item, name : String, weight : Int32, value : Int32, count : Int32

Line 973:

end

p "Total weight: #{w}, Value: #{val}"</~~lang~~>

p "Total weight: #{w}, Value: #{val}"</syntaxhighlight>

=={{header|D}}==

Solution with memoization.

<~~lang~~ d>import std.stdio, std.typecons, std.functional;

<syntaxhighlight lang="d">import std.stdio, std.typecons, std.functional;

immutable struct Item {

Line 1,034:

writeln("Total weight: ", w, " Value: ", v_lst[0]);

}</~~lang~~>

}</syntaxhighlight>

<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.

<~~lang~~ scheme>

(lib 'struct)

(lib 'sql)

Line 1,107:

(name i))))

</syntaxhighlight>

</lang>

<~~lang~~ scheme>

(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>

</lang>

=={{header|FreeBASIC}}==

<~~lang~~ freebasic>#define PesoMax 400

<syntaxhighlight lang="freebasic">#define PesoMax 400

#define items 22

#define Tabu Chr(9)

Line 1,192:

Print !"\nTotal value: "; TValor

Print "Total weight: "; PesoMax + TPeso

Sleep</~~lang~~>

Sleep</syntaxhighlight>

<pre>Knapsack contents:

Line 1,213:

=={{header|Go}}==

Solution with caching.

<~~lang~~ go>package main

<syntaxhighlight lang="go">package main

import "fmt"

Line 1,311:

}

fmt.Printf("Value: %d; weight: %d\n", v, w)

}</~~lang~~>

}</syntaxhighlight>

(A simple test and benchmark used while making changes to make sure performance wasn't sacrificed is available at [[/Go_test]].)

Line 1,330:

=={{header|Groovy}}==

Solution: dynamic programming

<~~lang~~ groovy>def totalWeight = { list -> list.collect{ it.item.weight * it.count }.sum() }

<syntaxhighlight lang="groovy">def totalWeight = { list -> list.collect{ it.item.weight * it.count }.sum() }

def totalValue = { list -> list.collect{ it.item.value * it.count }.sum() }

Line 1,347:

}

m[n][400]

}</~~lang~~>

}</syntaxhighlight>

Test:

<~~lang~~ groovy>def items = [

<syntaxhighlight lang="groovy">def items = [

[name:"map", weight: 9, value:150, pieces:1],

[name:"compass", weight: 13, value: 35, pieces:1],

Line 1,384:

printf (' item: %-22s weight:%4d value:%4d count:%2d\n',

it.item.name, it.item.weight, it.item.value, it.count)

}</~~lang~~>

}</syntaxhighlight>

<pre>Elapsed Time: 0.603 s

Line 1,403:

=={{header|Haskell}}==

Directly lifted from 1-0 problem:

<~~lang~~ haskell>inv = [("map",9,150,1), ("compass",13,35,1), ("water",153,200,2), ("sandwich",50,60,2),

<syntaxhighlight lang="haskell">inv = [("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), ("cream",11,70,1), ("camera",32,30,1),

Line 1,417:

new = map (\(val,itms)->(val + v * i, (name,i):itms)) old

main = print $ (knapsack inv) !! 400</~~lang~~>

main = print $ (knapsack inv) !! 400</syntaxhighlight>

Line 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):

<~~lang~~ haskell>import Data.Array

<syntaxhighlight lang="haskell">import Data.Array

-- snipped the item list; use the one from above

Line 1,434:

prepend (x,n) (y,s) = (x+y,n:s)

main = do print $ knapsack inv 400</~~lang~~>

main = do print $ knapsack inv 400</syntaxhighlight>

=={{header|J}}==

Brute force solution:

<~~lang~~ j>'names numbers'=:|:".;._2]0 :0

<syntaxhighlight lang="j">'names numbers'=:|:".;._2]0 :0

'map'; 9 150 1

'compass'; 13 35 1

Line 1,487:

bestCombo''

978832641</~~lang~~>

978832641</syntaxhighlight>

Interpretation of answer:

<~~lang~~ j> decode 978832641

<syntaxhighlight lang="j"> decode 978832641

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,506:

396

values +/ .* decode 978832641

1010</~~lang~~>

1010</syntaxhighlight>

Dynamic programming solution (faster):

<~~lang~~ j>dyn=:3 :0

<syntaxhighlight lang="j">dyn=:3 :0

m=. 0$~1+400,+/pieces NB. maximum value cache

b=. m NB. best choice cache

Line 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</~~lang~~>

1 1 1 0 2 0 3 0 1 0 1 0 0 0 0 0 1 1 1 0 1 0</syntaxhighlight>

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 ]].

<~~lang~~ java>package hu.pj.alg.test;

<syntaxhighlight lang="java">package hu.pj.alg.test;

import hu.pj.alg.BoundedKnapsack;

Line 1,621:

new BoundedKnapsackForTourists();

}

} // class</~~lang~~>

} // class</syntaxhighlight>

<~~lang~~ java>package hu.pj.alg;

<syntaxhighlight lang="java">package hu.pj.alg;

import hu.pj.obj.Item;

Line 1,684:

setInitialStateForCalculation();

}

} // class</~~lang~~>

} // class</syntaxhighlight>

<~~lang~~ java>package hu.pj.alg;

<syntaxhighlight lang="java">package hu.pj.alg;

import hu.pj.obj.Item;

Line 1,836:

solutionWeight = 0;

}

} // class</~~lang~~>

} // class</syntaxhighlight>

<~~lang~~ java>package hu.pj.obj;

<syntaxhighlight lang="java">package hu.pj.obj;

public class Item {

Line 1,905:

public int getInKnapsack() {return inKnapsack;}

public int getBounding() {return bounding;}

} // class</~~lang~~>

} // class</syntaxhighlight>

<pre>

Line 1,928:

=={{header|JavaScript}}==

Based on the (dynamic) J implementation. Expressed as an htm page:

<~~lang~~ javascript><html><head><title></title></head><body></body></html>

Line 2,006:

}

findBestPack();

</script></~~lang~~>

</script></syntaxhighlight>

This will generate (translating html to mediawiki markup):

{|

Line 2,077:

'''Works with gojq, the Go implementation of jq'''

<~~lang~~ jq># Item {name, weight, value, count}

<syntaxhighlight lang="jq"># Item {name, weight, value, count}

def Item($name; $weight; $value; $count): {$name, $weight, $value, $count};

Line 2,165:

task(400)

</syntaxhighlight>

</lang>

<pre>

Line 2,191:

'''Type and Function''':

<~~lang~~ julia>using MathProgBase, Cbc

<syntaxhighlight lang="julia">using MathProgBase, Cbc

struct KPDSupply{T<:Integer}

Line 2,219:

return pack

end

end</~~lang~~>

end</syntaxhighlight>

'''Main''':

<~~lang~~ julia>gear = [KPDSupply("map", 9, 150, 1),

<syntaxhighlight lang="julia">gear = [KPDSupply("map", 9, 150, 1),

KPDSupply("compass", 13, 35, 1),

KPDSupply("water", 153, 200, 2),

Line 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)), " €")</~~lang~~>

println("Packed value: ", sum(getfield.(pack, :value)), " €")</syntaxhighlight>

Line 2,269:

=={{header|Kotlin}}==

<~~lang~~ scala>// version 1.1.2

<syntaxhighlight lang="scala">// version 1.1.2

data class Item(val name: String, val weight: Int, val value: Int, val count: Int)

Line 2,350:

println("--------------------- ------ ----- ------")

println("Items chosen $itemCount ${"%3d".format(sumWeight)} ${"%4d".format(sumValue)} ${"%2d".format(sumNumber)}")

}</~~lang~~>

}</syntaxhighlight>

Line 2,372:

=={{header|Mathematica}}/{{header|Wolfram Language}}==

<~~lang~~ mathematica>Transpose@{#[[;; , 1]],

<syntaxhighlight lang="mathematica">Transpose@{#[[;; , 1]],

LinearProgramming[-#[[;; , 3]], -{#[[;; , 2]]}, -{400},

{0, #[[4]]} & /@ #, Integers]} &@{{"map", 9, 150, 1},

Line 2,395:

{"towel", 18, 12, 2},

{"socks", 4, 50, 1},

{"book", 30, 10, 2}}</~~lang~~>

{"book", 30, 10, 2}}</syntaxhighlight>

<pre>{{"map", 1}, {"compass", 1}, {"water", 1}, {"sandwich",

Line 2,406:

=={{header|Mathprog}}==

<~~lang~~ mathprog>/*Knapsack

<syntaxhighlight lang="mathprog">/*Knapsack

This model finds the integer optimal packing of a knapsack

Line 2,451:

;

end;</~~lang~~>

end;</syntaxhighlight>

The solution produced using glpk is here: [[Knapsack problem/Bounded/Mathprog]]

Line 2,460:

=={{header|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,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>

</lang>

<pre>

Line 2,492:

=={{header|Nim}}==

We expand the list of items and apply the 0-1 algorithm.

<~~lang~~ python># Knapsack. Recursive solution.

<syntaxhighlight lang="python"># Knapsack. Recursive solution.

import strformat

Line 2,600:

echo "Total weight: ", weight

echo "Total value: ", value

</syntaxhighlight>

</lang>

Line 2,654:

=={{header|OxygenBasic}}==

<~~lang~~ oxygenbasic>

type KnapSackItem string name,sys dag,value,tag

Line 2,765:

'

'Weight: 396

</syntaxhighlight>

</lang>

=={{header|Oz}}==

Using constraint programming.

<~~lang~~ oz>declare

<syntaxhighlight lang="oz">declare

%% maps items to tuples of

%% Weight(hectogram), Value and available Pieces

Line 2,837:

{System.printInfo "\n"}

{System.showInfo "total value: "#{Value Best}}

{System.showInfo "total weight: "#{Weight Best}}</~~lang~~>

{System.showInfo "total weight: "#{Weight Best}}</syntaxhighlight>

<pre>

Line 2,860:

=={{header|Perl}}==

Recursive solution with caching.

<~~lang~~ ~~Perl~~>#!/usr/bin/perl

<syntaxhighlight lang="perl">#!/usr/bin/perl

use strict;

Line 2,932:

}

print "Value: $v; Weight: $w\n";</~~lang~~>

print "Value: $v; Weight: $w\n";</syntaxhighlight>

<pre>1 of map

Line 2,950:

===Very dumb and very slow brute force version===

Of no practical use, except for comparison against improvements.

with javascript_semantics

atom t0 = time()

Line 3,016:

if points!=res[1] then ?9/0 end if -- sanity check

printf(1,"Value %d, weight %g [%3.2fs]\n",{points,weight,time()-t0})

<pre>

Line 3,035:

Much faster but limited to integer weights

with javascript_semantics

sequence items = {

Line 3,113:

end for

printf(1,"%-22s %5d %5d %5d\n", {"count, weight, points:", tc, tw, tv})

<pre>

Line 3,135:

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.

-- demo\rosetta\knapsackB.exw

with javascript_semantics

Line 3,277:

printf(1,"cache_entries:%d, hits:%d, misses:%d\n",{cache_entries,cache_hits,cache_misses})

<pre>

Line 3,309:

=={{header|Picat}}==

<~~lang~~ ~~Picat~~>import mip,util.

<syntaxhighlight lang="picat">import mip,util.

go =>

Line 3,389:

["socks", 4, 50, 1],

["book", 30, 10, 2]],

MaxWeight = 400.</~~lang~~>

MaxWeight = 400.</syntaxhighlight>

Line 3,410:

=={{header|PicoLisp}}==

<~~lang~~ ~~PicoLisp~~>(de *Items

<syntaxhighlight lang="picolisp">(de *Items

("map" 9 150 1) ("compass" 13 35 1)

("water" 153 200 3) ("sandwich" 50 60 2)

Line 3,441:

(for I K

(apply tab I (3 -24 6 6) NIL) )

(tab (27 6 6) NIL (sum cadr K) (sum caddr K)) )</~~lang~~>

(tab (27 6 6) NIL (sum cadr K) (sum caddr K)) )</syntaxhighlight>

<pre> map 9 150

Line 3,464:

Library clpfd is written by Markus Triska. Takes about 3 seconds to compute the best solution.

<~~lang~~ ~~Prolog~~>:- use_module(library(clpfd)).

<syntaxhighlight lang="prolog">:- use_module(library(clpfd)).

% tuples (name, weights, value, nb pieces).

Line 3,539:

sformat(W3, A3, [V]),

format('~w~w~w~w~n', [W0,W1,W2,W3]),

print_results(A1, A2, A3, T, TR, WM, VM).</~~lang~~>

print_results(A1, A2, A3, T, TR, WM, VM).</syntaxhighlight>

<pre> ?- knapsack.

Line 3,559:

===Library simplex===

Library simplex is written by Markus Triska. Takes about 10 seconds to compute the best solution.

<~~lang~~ ~~Prolog~~>:- use_module(library(simplex)).

<syntaxhighlight lang="prolog">:- use_module(library(simplex)).

% tuples (name, weights, value, pieces).

knapsack :-

Line 3,638:

W2 is W1 + X * W,

V2 is V1 + X * V),

print_results(S, A1, A2, A3, T, TN, W2, V2).</~~lang~~>

print_results(S, A1, A2, A3, T, TN, W2, V2).</syntaxhighlight>

=={{header|Python}}==

Not as [[Knapsack problem/0-1#Python|dumb a search]] over all possible combinations under the maximum allowed weight:

<~~lang~~ python>from itertools import groupby

<syntaxhighlight lang="python">from itertools import groupby

from collections import namedtuple

Line 3,692:

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:])</~~lang~~>

print("for a total value of %i and a total weight of %i" % bagged[1:])</syntaxhighlight>

<pre>Bagged the following 14 items

Line 3,709:

===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:

<~~lang~~ python>from itertools import groupby

<syntaxhighlight lang="python">from itertools import groupby

try:

Line 3,774:

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)))</~~lang~~>

sum(item[2] for item in bagged), sum(item[1] for item in bagged)))</syntaxhighlight>

===Non-zero-one solution===

<~~lang~~ ~~Python~~>items = {

<syntaxhighlight lang="python">items = {

"sandwich": (50, 60, 2),

"map": (9, 150, 1),

Line 3,834:

w = w + items[name][0] * cnt

print("Total weight:", w, "Value:", v)</~~lang~~>

print("Total weight:", w, "Value:", v)</syntaxhighlight>

=={{header|R}}==

Reading in task via web scraping.

<~~lang~~ R>library(tidyverse)

<syntaxhighlight lang="r">library(tidyverse)

library(rvest)

Line 3,849:

mutate(weight= as.numeric(weight),

value= as.numeric(value),

pieces= as.numeric(pieces))</~~lang~~>

pieces= as.numeric(pieces))</syntaxhighlight>

Solution of the task using genetic algorithm.

<~~lang~~ R>library(rgenoud)

<syntaxhighlight lang="r">library(rgenoud)

fitness= function(x= rep(1, nrow(task_table))){

Line 3,874:

cat("Weight:", sum(task_table$weight * evolution$par), "dag", "\n")

data.frame(item= task_table$items, pieces= as.integer(solution)) %>%

filter(solution> 0)</~~lang~~>

filter(solution> 0)</syntaxhighlight>

Line 3,899:

The algorithm is nearly a direct translation of Haskell's array-based implementation. However, the data is taken from the webpage itself.

#lang racket

(require net/url html xml xml/path)

Line 3,988:

(match-let ([(solution value choices) (best (vector->list (solution-vector capacity)))])

(solution value (filter (compose positive? choice-count) choices))))

</syntaxhighlight>

</lang>

Line 4,013:

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

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

<syntaxhighlight lang="raku" line>my class KnapsackItem { has $.name; has $.weight; has $.unit; }

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

Line 4,066:

for %hash.sort -> $item {

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

}</~~lang~~>

}</syntaxhighlight>

<pre>Value = 1010

Line 4,085:

==== Faster alternative ====

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

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

<syntaxhighlight lang="raku" line>my $raw = qq:to/TABLE/;

map 9 150 1

compass 13 35 1

Line 4,139:

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~~>

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

<pre>1 of map

Line 4,160:

"unrolled" and converted into discrete combination checks (based on the number of items).   The unused combinatorial

checks were discarded and only the pertinent code was retained.

<~~lang~~ rexx>/*REXX program solves a knapsack problem (22 items + repeats, with weight restriction.*/

<syntaxhighlight lang="rexx">/*REXX program solves a knapsack problem (22 items + repeats, with weight restriction.*/

call @gen /*generate items and initializations. */

call @sort /*sort items by decreasing their weight*/

Line 4,315:

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.*/</~~lang~~>

end;end;end;end;end;end;end;end;end;end; return /* [↑] there is one END for each DO loop.*/</syntaxhighlight>

'''output'''

<pre>

Line 4,374:

<~~lang~~ ruby>

# Item struct to represent each item in the problem

Struct.new('Item', :name, :weight, :value, :count)

Line 4,434:

p "Total weight: #{w}, Value: #{val}"

</syntaxhighlight>

</lang>

=={{header|SAS}}==

Use MILP solver in SAS/OR:

<~~lang~~ sas>/* create SAS data set */

<syntaxhighlight lang="sas">/* create SAS data set */

data mydata;

input item $1-23 weight value pieces;

Line 4,488:

print TotalValue;

print {i in ITEMS: NumSelected[i].sol > 0.5} NumSelected;

quit;</~~lang~~>

quit;</syntaxhighlight>

Output:

Line 4,511:

=={{header|Sidef}}==

<~~lang~~ ruby>var raw = <<'TABLE'

<syntaxhighlight lang="ruby">var raw = <<'TABLE'

map 9 150 1

compass 13 35 1

Line 4,577:

say "#{p[i]} of #{items[i].name}" if p[i].is_pos

}

say "Value: #{v}; Weight: #{w}"</~~lang~~>

say "Value: #{v}; Weight: #{w}"</syntaxhighlight>

<pre>

Line 4,598:

<~~lang~~ swift>public struct KnapsackItem: Hashable {

<syntaxhighlight lang="swift">public struct KnapsackItem: Hashable {

public var name: String

public var weight: Int

Line 4,679:

}

print("For a total value of \(totalVal) and weight of \(totalWeight)")</~~lang~~>

print("For a total value of \(totalVal) and weight of \(totalWeight)")</syntaxhighlight>

Line 4,703:

=={{header|Tcl}}==

Classic dumb search algorithm:

<~~lang~~ tcl># The list of items to consider, as list of lists

<syntaxhighlight lang="tcl"># The list of items to consider, as list of lists

set items {

{map 9 150 1}

Line 4,789:

foreach {count item} [countednames $best] {

puts "\t$count * $item"

}</~~lang~~>

}</syntaxhighlight>

<pre>

Line 4,810:

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.

<~~lang~~ ~~Ursala~~>#import std

<syntaxhighlight lang="ursala">#import std

#import flo

#import lin

Line 4,853:

#show+

main = format solution system items</~~lang~~>

main = format solution system items</syntaxhighlight>

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,877:

<~~lang~~ ecmascript>import "/fmt" for Fmt

<syntaxhighlight lang="ecmascript">import "/fmt" for Fmt

class Item {

Line 4,969:

}

System.print("--------------------- ------ ----- ------")

Fmt.print("Items chosen $d $3d $4d $2d", itemCount, sumWeight, sumValue, sumNumber)</~~lang~~>

Fmt.print("Items chosen $d $3d $4d $2d", itemCount, sumWeight, sumValue, sumNumber)</syntaxhighlight>

Line 4,992:

=={{header|zkl}}==

<~~lang~~ zkl>fcn addItem(old,[(nm,w,v,c)]){ // old:list:(cost of:,(name,#,...))

<syntaxhighlight lang="zkl">fcn addItem(old,[(nm,w,v,c)]){ // old:list:(cost of:,(name,#,...))

[1..c].reduce(fcn(list,i,nm,w,v,old){

wi,left,right:=w*i,list[0,wi],list[wi,*];

Line 4,999:

fcn([(v1,_)]a,[(v2,_)]b){ v1>v2 and a or b },new));

},old,nm,w,v,old);

}//--> new list</~~lang~~>

}//--> new list</syntaxhighlight>

<~~lang~~ zkl>items:=T( // item: (name,weight,value,#)

<syntaxhighlight lang="zkl">items:=T( // item: (name,weight,value,#)

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 5,013:

'wrap(nm,n){ items[items.filter1n(fcn(it,nm){ it[0]==nm },nm)][1]*n })

.sum(0)

};</~~lang~~>

};</syntaxhighlight>

<~~lang~~ zkl>const MAX_WEIGHT=400;

<syntaxhighlight lang="zkl">const MAX_WEIGHT=400;

knapsack:=items.reduce(addItem,(MAX_WEIGHT).pump(List,T(0,T).copy))[-1];

knapsack.toString(*).println(weight(knapsack));</~~lang~~>

knapsack.toString(*).println(weight(knapsack));</syntaxhighlight>

<pre>