Knapsack problem/Continuous: Difference between revisions

{{trans|Python}}

(‘pork’, 5.4, 43.0),

(‘ham’, 3.6, 90.0),

print(‘ ITEM PORTION VALUE’)

print(bagged.map((n, p, a) -> ‘#10 #3.2 #3.2’.format(n, p, a)).join("\n"))

{{out}}

=={{header|Ada}}==

with Ada.Float_Text_IO;

with Ada.Strings.Unbounded;

end loop;

end Knapsack_Continuous;

{{out}}

<pre>

=={{header|AWK}}==

BEGIN {

# arr["item,weight,price"]

exit(0)

}

{{out}}

<pre>

=={{header|BBC BASIC}}==

{{works with|BBC BASIC for Windows}}

Sort% = FN_sortSAinit(1, 0) : REM Descending

PRINT '"Total weight = " ; TotalWeight " kg"

PRINT "Total price = " ; TotalPrice

Output:

<pre>Take all the salami

The table of weights and prices are stored as strings to make them easier to edit. Two characters for the weight (with the decimal point dropped), two characters for the price, and then the name of the item. The total numbers of items (9) is specified by the first value on the stack.

>\`!v|:-1p\3\0p\2\+-*86g\3\*+55-*86g\2<<1v*g21\*g2<

nib@_>0022p6>12p:212gg48*:**012gg/\-:0`3^+>,,55+%6v

3767welt

3095salami

{{out}}

=={{header|Bracmat}}==

The second argument is the number of decimals. }

= value decimals powerOf10

| out$(fixed$(!totalPrice.2))

)

Output:<pre>3.5 kg of welt

2.4 kg of greaves

=={{header|C}}==

#include <stdlib.h>

return 0;

take all salami

take all ham

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

class Program

{

static string[] items = {"beef","pork","ham","greaves","flitch",

"brawn","welt","salami","sausage"};

Sorting three times is expensive,

an alternative is sorting once, with an indices array.

class Program

{

static string[] items = {"beef","pork","ham","greaves","flitch",

"brawn","welt","salami","sausage"};

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

#include<algorithm>

#include<string.h>

return 0;

{{out}}

===Alternate Version===

#include <iostream>

#include <vector>

space -= item.weight;

}

{{out}}

=={{header|Clojure}}==

; Solve Continuous Knapsack Problem

; Nicolas Modrzyk

(rob items maxW)

Output<pre>

Take all :salami

===Alternate Version===

(def items

[{:name "beef" :weight 3.8 :price 36}

(rob items 15)

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

(name nil :type string)

(weight nil :type real)

(make-item :name "sausage" :weight 5.9 :price 98))))

(loop for (name amount) in (knapsack items 15)

{{out}}

<pre>salami : 3.00 kg

=={{header|D}}==

struct Item {

writefln("%(%s\n%)", chosen);

Item("TOTAL", chosen.sumBy!"amount", chosen.sumBy!"value").writeln;

{{out}}

<pre> ITEM AMOUNT VALUE $/unit

===Alternative Version===

import std.stdio, std.algorithm;

} else

return writefln("Take %.1fkg %s", left, it.item);

{{out}}

<pre>Take all the salami

=={{header|EchoLisp}}==

(lib 'struct)

(lib 'sql) ;; for table

=={{header|Eiffel}}==

class

CONTINUOUS_KNAPSACK

end

{{out}}

<pre>

=={{header|Elixir}}==

{{trans|Erlang}}

def select( max_weight, items ) do

Enum.sort_by( items, fn {_name, weight, price} -> - price / weight end )

{"sausage", 5.9, 98} ]

{{out}}

===Alternate Version===

{{trans|Ruby}}

def continuous(items, max_weight) do

Enum.sort_by(items, fn {_item, {weight, price}} -> -price / weight end)

sausage: {5.9, 98} ]

{{out}}

=={{header|Erlang}}==

Note use of lists:foldr/2, since sort is ascending.

-module( knapsack_problem_continuous ).

select_until_weight( Weight, Remains ) when Weight < Remains -> Weight;

select_until_weight( _Weight, Remains ) -> Remains.

{{out}}

<pre>

=={{header|F_Sharp|F#}}==

//Fill a knapsack optimally - Nigel Galloway: February 1st., 2015

let items = [("beef", 3.8, 36);("pork", 5.4, 43);("ham", 3.6, 90);("greaves", 2.4, 45);("flitch" , 4.0, 30);("brawn", 2.5, 56);("welt", 3.7, 67);("salami" , 3.0, 95);("sausage", 5.9, 98)]

| [] -> printfn "Everything taken! Total value of swag is £%0.2f; Total weight of bag is %0.2fkg" a n

take(0.0, items, 0.0)

{{out}}

<pre>

{{trans|D}}

{{works with|4tH|3.62.0}}

150 value left \ capacity in 1/10th kilo

;

=={{header|Fortran}}==

{{works with|Fortran|90 and later}}

implicit none

write(*, "(f15.2, f8.2)") total_weight, total_value

=={{header|FreeBASIC}}==

Type Knapsack

articulo As String*7

Print Using "Total weight: ###.## kg"; TPeso

Print Using "Total value: ###.##"; TPrecio

{{out}}

<pre>You can carry the following materials in the knapsack:

=={{header|GNU APL}}==

Items←'beef' 'pork' 'ham' 'greaves' 'flitch' 'brawn' 'welt' 'salami' 'sausage'

Weights←3.8 5.4 3.6 2.4 4 2.5 3.7 3 5.9

⎕←''

⎕←'total cost:' TotalCost

{{out}}

<pre>

=={{header|Go}}==

import (

}

}

Output:

<pre>

=={{header|Groovy}}==

Solution: obvious greedy algorithm

def knapsackCont = { list, maxWeight = 15.0 ->

}

sack

Test:

[name:'beef', weight:3.8, value:36],

[name:'pork', weight:5.4, value:43],

contents.each {

printf(" name: %-7s weight: ${it.weight} value: ${it.value}\n", it.name)

Output:

We use a greedy algorithm.

import Data.Ord (comparing)

import Text.Printf (printf)

where

a = floor q

{{Out}}

<pre>3 kg of salami

Or similar to above (but more succinct):

import Data.Ord (comparing)

import Text.Printf (printf)

| otherwise = printf "Take %.2f kg of the %s\n" (k :: Float) name

{{Out}}

<pre>Take all the salami

=={{header|Icon}} and {{header|Unicon}}==

This implements the greedy algorithm. This also uses a Unicon extension to ''reverse'' which reverses a list. In Icon, an IPL procedure is available to do the same.

procedure main()

item("salami", 3.0, 95),

item("sausage", 5.9, 98) ]

{{libheader|Icon Programming Library}}

We take as much as we can of the most valuable items first, and continue until we run out of space. Only one item needs to be cut.

beef 3.8 36

pork 5.4 43

order=: \:prices%weights

take=: 15&<.&.(+/\) order{weights

This gives the result:

For a total value of:

See [[Knapsack_problem/Continuous/J]] for some comments on intermediate results...

Greedy solution.

package hu.pj.alg.test;

}

package hu.pj.alg;

}

package hu.pj.obj;

}

output:

{{ works with|jq|1.4}}

# an array of objects {"name": _, "weight": _, "value": _}

# where "value" is the value of the given weight of the object.

| (.[] | {name, weight}),

"Total value: \( map(.value) | add)",

'''The task:'''

{ "name": "beef", "weight": 3.8, "value": 36},

{ "name": "pork", "weight": 5.4, "value": 43},

{ "name": "sausage", "weight": 5.9, "value": 98} ];

{{out}}

{"name":"salami","weight":3}

{"name":"ham","weight":3.6}

{"name":"welt","weight":3.5000000000000004}

Total value: 349.3783783783784

=={{header|Julia}}==

'''Type and Functions''':

struct KPCSupply{T<:Real}

end

return sack

'''Main''':

KPCSupply("pork", 54//10, 43),

KPCSupply("ham", 36//10, 90),

println("The store contains:\n - ", join(store, "\n - "))

println("\nThe thief should take::\n - ", join(sack, "\n - "))

{{out}}

=={{header|Kotlin}}==

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

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

println("${itemCount} items 15.0 ${"%6.2f".format(sumValue)}")

{{out}}

=={{header|M2000 Interpreter}}==

Module Knapsack {

Form 60, 40

}

Knapsack

Output the same as other examples, with some color.

The output is then all items prior to this one, along with that item corrected for it's excess weighter (overW)

sortedTable = SortBy[{#1, #2, #3, #3/#2} & @@@ shop, -#[[4]] &];

overN = Position[Accumulate[sortedTable[[1 ;;, 2]]], a_ /; a > capacity, 1,1][[1, 1]];

output[[-1, 2]] = output[[-1, 2]] - overW;

output[[-1, 3]] = output[[-1, 2]] output[[-1, 4]];

A test using the specified data:

{{"beef", 3.8, 36}, {"pork", 5.4, 43}, {"ham", 3.6, 90}, {"greaves", 2.4, 45}, {"flitch", 4., 30},

{"brawn", 2.5, 56}, {"welt", 3.7, 67}, {"salami", 3., 95}, {"sausage", 5.9, 98}};

welt 3.5 63.3784

Total 15. 349.378

=={{header|Mathprog}}==

This model finds the optimal packing of a knapsack

sausage 5.9 98

;

The solution is here at [[Knapsack problem/Continuous/Mathprog]].

=={{header|MiniZinc}}==

%Knapsack Continuous. Nigel Galloway: October 7th., 2020.

enum Items={beef,pork,ham,greaves,flitch,brawn,welt,salami,sausage};

solve maximize wValue;

output[concat([let {string: g=show(quantity[n])} in "Take "++(if g==show(weight[n]) then "all" else g endif)++" of \(n)\n" | n in Items where show(quantity[n])!="0.0"])++"\nTotal Weight=\(wTaken) Total Value="++show_float(4,2,wValue)]

{{out}}

<pre>

</pre>

=={{header|Nim}}==

import strformat

break

{{out}}

=={{header|OCaml}}==

[ "beef", 3.8, 36;

"pork", 5.4, 43;

Printf.printf " %7s: %6.2f %6.2f\n" last rem_weight last_price;

Printf.printf " Total Price: %.3f\n" (float price +. last_price);

{{out}}

=={{header|Oforth}}==

[ "beef", 3.8, 36 ], [ "pork", 5.4, 43 ], [ "ham", 3.6, 90 ],

[ "greaves", 2.4, 45 ], [ "flitch", 4.0, 30 ], [ "brawn", 2.5, 56 ],

"And part of" . item first . " :" . dup .cr

item third * item second / value + "Total value :" . .cr break

{{out}}

=={{header|ooRexx}}==

===version 1===

* 20.09.2014 Walter Pachl translated from REXX version 2

* utilizing ooRexx features like objects, array(s) and sort

Otherwise res='-1'

End

{{out}}

<pre>

total 15.000 349.378</pre>

===version 2===

* 20.09.2014 Walter Pachl translated from REXX version 2

* utilizing ooRexx features like objects, array(s) and sort

Expose vpu

use Arg other

Output is the same as for version 1.

=={{header|Perl}}==

(

[qw'beef 3.8 36'],

print "-" x 40, "\ntotal value: $value\n";

Output:<pre>item fraction weight value

salami all 3.0 95

=={{header|Phix}}==

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">constant</span> <span style="color: #000000;">meats</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span>

<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;">"Total value: %f\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">worth</span><span style="color: #0000FF;">})</span>

{{out}}

<pre>

=={{header|PHP}}==

$data = [

[

$limit -= $item['weight'];

endforeach;

Output:

<pre>Take all the salami

=={{header|Picat}}==

items(Items),

weights(Weights),

items([beef,pork,ham,greaves,flitch,brawn,welt,salami,sausage]).

weights([3.8,5.4,3.6,2.4,4.0,2.5,3.7,3.0,5.9]).

{{out}}

=={{header|PicoLisp}}==

(de *Items

NIL

(format (sum cadr K) *Scl)

Output:

<pre> salami 3.00 95.00

=={{header|PL/I}}==

KNAPSACK_CONTINUOUS: Proc Options(main);

/*--------------------------------------------------------------------

item(i).value = value;

End;

{{out}}

<pre>

=={{header|Prolog}}==

Works with SWI-Prolog and <b>library(simplex)</b> written by <b>Markus Triska</b>

% tuples (name, weights, value).

knapsack :-

print_results(S, A1, A2, A3, T, TN, W2, V2).

Output :

<pre> ?- knapsack.

=={{header|PureBasic}}==

Using the greedy algorithm.

name.s

weight.f ;units are kilograms (kg)

Input()

CloseConsole()

Sample output:

<pre>Maximal weight = 15 kg

=={{header|Python}}==

I think this greedy algorithm of taking the largest amounts of items ordered by their value per unit weight is maximal:

items = [("beef", 3.8, 36.0),

("pork", 5.4, 43.0),

print(" ITEM PORTION VALUE")

print("\n".join("%10s %6.2f %6.2f" % item for item in bagged))

'''Sample Output'''

=={{header|R}}==

Translated into r-script by Shana White (vandersm@mail.uc.edu) from pseudocode found in 'Algorithms: Sequential Parallel and Distributed', by Kenneth A. Berman and Jerome L. Paul

knapsack<- function(Value, Weight, Objects, Capacity){

Fraction = rep(0, length(Value))

print("Total value of tasty meats:")

print(Total_Value)

'''Sample Input'''

=={{header|Racket}}==

(define shop-inventory

'((beef 3.8 36)

(call-with-values (lambda () (continuous-knapsack shop-inventory null 15 0))

{{out}}

{{works with|rakudo|2015-09-16}}

This Solutions sorts the item by WEIGHT/VALUE

has $.name;

has $.weight is rw;

$max-w -= .weight;

last if $last-one;

'''Output:'''

<pre>Item Portion Value

Originally used the Fortran program as a prototype.

<br>Some amount of code was added to format the output better.

@.= /*═══════ name weight value ══════*/

@.1 = 'flitch 4 30 '

syf: call sy arg(1), $(format(arg(2), , d)), $(format(arg(3), , d)); return

title: call sy center('item',nL), center("weight", wL), center('value', vL); return

'''output''' &nbsp; using the default inputs of: &nbsp; <tt> 15 &nbsp; 3 </tt>

<pre>

===version 2===

* 19.09.2014 Walter Pachl translated from FORTRAN

* While this program works with all REXX interpreters,

input.i=name'*'weight'*'value

input.0=i

{{out}}

<pre># vpu name weight value

=={{header|Ruby}}==

[:pork , 5.4, 43],

[:ham , 3.6, 90],

break

end

{{out}}

<pre>

=={{header|Run BASIC}}==

{{incorrect|Run BASIC}}

dim wgt(9)

dim price(9)

print "-------- Total ";using("###.#",totTake);chr$(9);"Weight: ";totWgt

end if

<pre>Best 2 Options

=={{header|Rust}}==

let items: [(&str, f32, u8); 9] = [

("beef", 3.8, 36),

}

}

Grab 3.0 kgs of salami

Grab 3.6 kgs of ham

=={{header|SAS}}==

Use LP solver in SAS/OR:

data mydata;

input item $ weight value;

print TotalValue;

print {i in ITEMS: WeightSelected[i].sol > 1e-3} WeightSelected;

Output:

=={{header|Scala}}==

===Functional approach (Tail recursive)===

object ContinousKnapsackForRobber extends App {

println(packer(sortedItems, Lootsack(Nil)))

{{Out}}

<pre>100.00% Salami 3.0 95.00

=={{header|Sidef}}==

{{trans|Perl}}

[

[:beef, 3.8, 36],

}

{{out}}

<pre>

=={{header|Tcl}}==

# Uses the trivial greedy algorithm

# We return the total value too, purely for convenience

return [list $result $totalValue]

Driver for this particular problem:

{beef 3.8 36}

{pork 5.4 43}

lassign $item name mass value

puts [format "\t%.1fkg of %s, value %.2f" $mass $name $value]

Output:

<pre>

[http://www.gnu.org/software/glpk/glpk.html glpk] depending on the

[http://www.basis.netii.net/avram run-time system] configuration).

#import lin

#cast %em

output:

<pre><

=={{header|Vlang}}==

item string

weight f64

}

//println(items)

{{out}}

<pre>

{{libheader|Wren-math}}

{{libheader|Wren-sort}}

import "/math" for Math

import "/sort" for Sort

}

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

{{out}}

=={{header|XPL0}}==

real Weight, Best, ItemWt, TotalWt;

def Items = 9;

Text(0, Name(BestItem)); CrLf(0);

until TotalWt >= 15.0; \all we can steal

Output:

=={{header|zkl}}==

{{trans|C}}

T(3.6, 90.0, "ham"), T(2.4, 45.0, "greaves"),

T(4.0, 30.0, "flitch"),T(2.5, 56.0, "brawn"),

if (space >= w){ println("take all ",nm); space-=w }

else{ println("take %gkg of %gkg of %s".fmt(space,w,nm)); break }

{{out}}

<pre>