Knapsack problem/Continuous: Difference between revisions

This is the item list in the butcher's shop:

 

|+ Table of potential knapsack items

|- style="background-color: rgb(255, 204, 255);"

*   Wikipedia article:   [[wp:Continuous_knapsack_problem|continuous knapsack]].

<br><br>

 

=={{header|Ada}}==

with Ada.Float_Text_IO;

with Ada.Strings.Unbounded;

end loop;

end Knapsack_Continuous;

{{out}}

<pre>

2.40 of greaves

3.50 of welt

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

</pre>

 

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

Take 3.5kg of welt

</pre>

 

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

Take all the greaves

Take 3.5kg welt</pre>

 

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

3.00 of "salami"

</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|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}}

Take (3.500000 kg) of the welt worth $63.378378

Total value of a full knapsack is $349.378378</pre>

 

=={{header|J}}==

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

item::String

weight::T

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

{{trans|Fortran}}

Using QuickSort (a generic form, non recursive)

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

Module Knapsack {

Form 60, 40

}

Knapsack

Output the same as other examples, with some color.

 

 

The problem is solved by sorting the original table by price to weight ratio, finding the accumlated weight, and the index of the item which exedes the carrying capacity (overN)

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|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);

 

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

</pre>

 

 

 

 

 

 

 

 

 

 

{{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}}

Take 3.50 of the welt (for 63.38)

For a grand total of: 349.38</pre>

 

=={{header|REXX}}==

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

-----------------------

total 15.000 349.378</pre>

 

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

 

salami Value: 475.0 Weight: 15.0

-------- Total 475.0 Weight: 15.0</pre>

 

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

salami 3.0

welt 3.5 </pre>

=={{header|Scala}}==

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

 

object ContinousKnapsackForRobber extends App {

 

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

{{Out}}

<pre>100.00% Salami 3.0 95.00

Totals: weight: 15.0, value: 349.38</pre>

{{Out}}See it in running in your browser by [https://scalafiddle.io/sf/RHZQ4Xj/1 ScalaFiddle (JavaScript)] <!--or by [https://scastie.scala-lang.org/mDoBS77YSG2Z7w5xdAPzcw Scastie (JVM)]-->.

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

'salami ': 3.000000e+00,

'welt ': 3.500000e+00></pre>

 

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