Knapsack problem/Continuous: Difference between revisions

{{task|Classic CS problems and programs}}

 

 

 

 

|+ Table of potential knapsack items

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

|}

 

 

 

 

procedure Knapsack_Continuous is

package US renames Ada.Strings.Unbounded;

type Item is record

Name : US.Unbounded_String;

Taken : Float;

end record;

function "<" (Left, Right : Item) return Boolean is

begin

Float (Right.Value) / Right.Weight;

end "<";

type Item_Array is array (Positive range <>) of Item;

function Total_Weight (Items : Item_Array) return Float is

Sum : Float := 0.0;

begin

for I in Items'Range loop

end loop;

return Sum;

end Total_Weight;

function Total_Value (Items : Item_Array) return Float is

Sum : Float := 0.0;

begin

for I in Items'Range loop

end loop;

return Sum;

end Total_Value;

procedure Solve_Knapsack_Continuous

(Items : in out Item_Array;

end;

end Solve_Knapsack_Continuous;

((US.To_Unbounded_String ("beef"), 3.8, 36, 0.0),

(US.To_Unbounded_String ("pork"), 5.4, 43, 0.0),

(US.To_Unbounded_String ("salami"), 3.0, 95, 0.0),

(US.To_Unbounded_String ("sausage"), 5.9, 98, 0.0));

begin

Solve_Knapsack_Continuous (All_Items, 15.0);

Ada.Text_IO.Put_Line ("Items:");

for I in All_Items'Range loop

if All_Items (I).Taken > 0.0 then

end if;

end loop;

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

Take all the ham

Take all the brawn

Total price = 349.378379

</pre>

 

=={{header|Bracmat}}==

The second argument is the number of decimals. }

= value decimals powerOf10

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

)

2.4 kg of greaves

2.5 kg of brawn

 

=={{header|C}}==

#include <stdlib.h>

 

 

return 0;

take all salami

take all ham

take 3.5kg of 3.7 kg of welt

</pre>

 

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

#include<algorithm>

#include<string.h>

 

return 0;

 

 

===Alternate Version===

#include <iostream>

#include <vector>

space -= item.weight;

}

 

=={{header|D}}==

 

struct Item {

}

 

return format("%10s %7.2f %7.2f %7.2f",

name, amount, value, valuePerKG);

}

 

return reduce!("a + b." ~ field)(0.0L, items);

}

 

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

Item("pork", 5.4, 43.0),

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

</pre>

 

 

=={{header|Forth}}==

{{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 Data.Ratio (numerator, denominator)

 

maxWgt = 15

 

data Bounty = Bounty

 

 

solution :: [(Rational, Bounty)]

solution = g maxWgt $ sortBy (flip $ comparing f) items

 

main = do

 

Or similar to above (but more succinct):

import Data.Ord (comparing)

import Text.Printf (printf)

 

-- (name, (value, weight))

 

 

solution k = loop k . sortBy (flip $ comparing unitWeight)

 

 

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

 

=={{header|Java}}==

Greedy solution.

 

package hu.pj.alg.test;

 

}

 

 

package hu.pj.alg;

 

}

 

 

package hu.pj.obj;

 

}

 

 

output:

3,5 kg welt (value = 63,378)</pre>

 

 

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

 

 

[ "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|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>

 

 

 

 

 

 

 

=={{header|PicoLisp}}==

 

(de *Items

NIL

(format (sum cadr K) *Scl)

Output:

<pre> salami 3.00 95.00

welt 3.50 63.38

15.00 349.38</pre>

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

TOTAL WEIGHT: 15.00

TOTAL VALUE: 349.38</pre>

 

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

===version 1===

Originally used the Fortran program as a prototype.

────────────────unsorted item list────────────────

 

 

 

───────────burglar's knapsack contents────────────

 

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

else

break

end

{{out}}

<pre>

Take all brawn

Take all greaves

 

</pre>

 

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

3.5 kg of welt

</pre>

 

[[Category:Puzzles]]