Knapsack problem/Continuous: Difference between revisions

Content added Content deleted
(Rename Perl 6 -> Raku, alphabetize, minor clean-up)
Line 166: Line 166:
2.40 of greaves
2.40 of greaves
3.50 of welt
3.50 of welt
</pre>

=={{header|GNU APL}}==
<lang APL>⍝ Data
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
Prices←36 43 90 45 30 56 67 95 98

⍝ Solution
Order←⍒Worth←Prices÷Weights ⍝ 'Worth' is each item value for 1 kg.
diff←{¯1↓(⍵,0)-0,⍵} ⍝ 'diff' between each item and the prev item (the inverse of '+\').
Filter←×Selected←diff 15⌊+\Weights[Order] ⍝ 'Selected' weights totaling 15kg, others 0.
Table←⊃{⍺,⍪⍵}/Items Weights Selected[⍋Order]
Take←Filter[⍋Order]/[1]Table
TotalCost←+/Prices×Selected[⍋Order]÷Weights

⍝ Output
⎕←'ITEM' 'WEIGHT AVAILABLE' 'WEIGHT SELECTED' ⍪ Take
⎕←''
⎕←'total cost:' TotalCost
</lang>
{{out}}
<pre>
ITEM WEIGHT AVAILABLE WEIGHT SELECTED
ham 3.6 3.6
greaves 2.4 2.4
brawn 2.5 2.5
welt 3.7 3.5
salami 3 3

total cost: 349.3783784
</pre>
</pre>


Line 436: Line 405:
</pre>
</pre>


=={{header|C#}}==
=={{header|C sharp|C#}}==
<lang csharp>using System; //4790@3.6
<lang csharp>using System; //4790@3.6
class Program
class Program
Line 505: Line 474:
"brawn","welt","salami","sausage"};
"brawn","welt","salami","sausage"};
}</lang>
}</lang>

=={{header|Clojure}}==
<lang Clojure>
; Solve Continuous Knapsack Problem
; Nicolas Modrzyk
; January 2015

(def maxW 15.0)
(def 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]})

(defn rob [items maxW]
(let[
val-item
(fn[key]
(- (/ (second (items key)) (first (items key )))))
compare-items
(fn[key1 key2]
(compare (val-item key1) (val-item key2)))
sorted (into (sorted-map-by compare-items) items)]
(loop [current (first sorted)
array (rest sorted)
value 0
weight 0]
(let[new-weight (first (val current))
new-value (second (val current))]
(if (> (- maxW weight new-weight) 0)
(do
(println "Take all " (key current))
(recur
(first array)
(rest array)
(+ value new-value)
(+ weight new-weight)))
(let [t (- maxW weight)] ; else
(println
"Take " t " of "
(key current) "\n"
"Total Value is:"
(+ value (* t (/ new-value new-weight))))))))))

(rob items maxW)
</lang>
Output<pre>
Take all :salami
Take all :ham
Take all :brawn
Take all :greaves
Take 3.5 of :welt
Total Value is: 349.3783783783784
</pre>

===Alternate Version===
<lang Clojure>
(def items
[{:name "beef" :weight 3.8 :price 36}
{:name "pork" :weight 5.4 :price 43}
{:name "ham" :weight 3.6 :price 90}
{:name "graves" :weight 2.4 :price 45}
{:name "flitch" :weight 4.0 :price 30}
{:name "brawn" :weight 2.5 :price 56}
{:name "welt" :weight 3.7 :price 67}
{:name "salami" :weight 3.0 :price 95}
{:name "sausage" :weight 5.9 :price 98}])

(defn per-kg [item] (/ (:price item) (:weight item)))

(defn rob [items capacity]
(let [best-items (reverse (sort-by per-kg items))]
(loop [items best-items cap capacity total 0]
(let [item (first items)]
(if (< (:weight item) cap)
(do (println (str "Take all " (:name item)))
(recur (rest items) (- cap (:weight item)) (+ total (:price item))))
(println (format "Take %.1f kg of %s\nTotal: %.2f monies"
cap (:name item) (+ total (* cap (per-kg item))))))))))

(rob items 15)
</lang>


=={{header|C++}}==
=={{header|C++}}==
Line 766: Line 647:
Take 3.5kg of welt
Take 3.5kg of welt
</pre>
</pre>

=={{header|Clojure}}==
<lang Clojure>
; Solve Continuous Knapsack Problem
; Nicolas Modrzyk
; January 2015

(def maxW 15.0)
(def 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]})

(defn rob [items maxW]
(let[
val-item
(fn[key]
(- (/ (second (items key)) (first (items key )))))
compare-items
(fn[key1 key2]
(compare (val-item key1) (val-item key2)))
sorted (into (sorted-map-by compare-items) items)]
(loop [current (first sorted)
array (rest sorted)
value 0
weight 0]
(let[new-weight (first (val current))
new-value (second (val current))]
(if (> (- maxW weight new-weight) 0)
(do
(println "Take all " (key current))
(recur
(first array)
(rest array)
(+ value new-value)
(+ weight new-weight)))
(let [t (- maxW weight)] ; else
(println
"Take " t " of "
(key current) "\n"
"Total Value is:"
(+ value (* t (/ new-value new-weight))))))))))

(rob items maxW)
</lang>
Output<pre>
Take all :salami
Take all :ham
Take all :brawn
Take all :greaves
Take 3.5 of :welt
Total Value is: 349.3783783783784
</pre>

===Alternate Version===
<lang Clojure>
(def items
[{:name "beef" :weight 3.8 :price 36}
{:name "pork" :weight 5.4 :price 43}
{:name "ham" :weight 3.6 :price 90}
{:name "graves" :weight 2.4 :price 45}
{:name "flitch" :weight 4.0 :price 30}
{:name "brawn" :weight 2.5 :price 56}
{:name "welt" :weight 3.7 :price 67}
{:name "salami" :weight 3.0 :price 95}
{:name "sausage" :weight 5.9 :price 98}])

(defn per-kg [item] (/ (:price item) (:weight item)))

(defn rob [items capacity]
(let [best-items (reverse (sort-by per-kg items))]
(loop [items best-items cap capacity total 0]
(let [item (first items)]
(if (< (:weight item) cap)
(do (println (str "Take all " (:name item)))
(recur (rest items) (- cap (:weight item)) (+ total (:price item))))
(println (format "Take %.1f kg of %s\nTotal: %.2f monies"
cap (:name item) (+ total (* cap (per-kg item))))))))))

(rob items 15)
</lang>


=={{header|Common Lisp}}==
=={{header|Common Lisp}}==
Line 1,166: Line 1,135:
3.00 of "salami"
3.00 of "salami"
</pre>
</pre>



=={{header|F_Sharp|F#}}==
=={{header|F_Sharp|F#}}==
Line 1,314: Line 1,282:
end program KNAPSACK_CONTINUOUS</lang>
end program KNAPSACK_CONTINUOUS</lang>

=={{header|GNU APL}}==
<lang APL>⍝ Data
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
Prices←36 43 90 45 30 56 67 95 98

⍝ Solution
Order←⍒Worth←Prices÷Weights ⍝ 'Worth' is each item value for 1 kg.
diff←{¯1↓(⍵,0)-0,⍵} ⍝ 'diff' between each item and the prev item (the inverse of '+\').
Filter←×Selected←diff 15⌊+\Weights[Order] ⍝ 'Selected' weights totaling 15kg, others 0.
Table←⊃{⍺,⍪⍵}/Items Weights Selected[⍋Order]
Take←Filter[⍋Order]/[1]Table
TotalCost←+/Prices×Selected[⍋Order]÷Weights

⍝ Output
⎕←'ITEM' 'WEIGHT AVAILABLE' 'WEIGHT SELECTED' ⍪ Take
⎕←''
⎕←'total cost:' TotalCost
</lang>
{{out}}
<pre>
ITEM WEIGHT AVAILABLE WEIGHT SELECTED
ham 3.6 3.6
greaves 2.4 2.4
brawn 2.5 2.5
welt 3.7 3.5
salami 3 3

total cost: 349.3783784
</pre>


=={{header|Go}}==
=={{header|Go}}==
Line 1,567: Line 1,566:
Take (3.500000 kg) of the welt worth $63.378378
Take (3.500000 kg) of the welt worth $63.378378
Total value of a full knapsack is $349.378378</pre>
Total value of a full knapsack is $349.378378</pre>



=={{header|J}}==
=={{header|J}}==
Line 2,020: Line 2,018:
{{trans|Fortran}}
{{trans|Fortran}}
Using QuickSort (a generic form, non recursive)
Using QuickSort (a generic form, non recursive)

=={{header|M2000 Interpreter}}==
=={{header|M2000 Interpreter}}==
<lang M2000 Interpreter>
<lang M2000 Interpreter>
Line 2,464: Line 2,463:
----------------------------------------
----------------------------------------
total value: 349.378378378378
total value: 349.378378378378
</pre>

=={{header|Perl 6}}==
{{works with|rakudo|2015-09-16}}
This Solutions sorts the item by WEIGHT/VALUE
<lang perl6>class KnapsackItem {
has $.name;
has $.weight is rw;
has $.price is rw;
has $.ppw;

method new (Str $n, Rat $w, Int $p) {
self.bless(:name($n), :weight($w), :price($p), :ppw($w/$p))
}

method cut-maybe ($max-weight) {
return False if $max-weight > $.weight;
$.price = $max-weight / $.ppw;
$.weight = $.ppw * $.price;
return True;
}

method gist () { sprintf "%8s %1.2f %3.2f",
$.name,
$.weight,
$.price }
}

my $max-w = 15;
say "Item Portion Value";

.say for gather
for < 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 >
==> map({ KnapsackItem.new($^a, $^b, $^c) })
==> sort *.ppw
{
my $last-one = .cut-maybe($max-w);
take $_;
$max-w -= .weight;
last if $last-one;
}</lang>
'''Output:'''
<pre>
%perl6 knapsack_continous.p6
Item Portion Value
salami 3.00 95.00
ham 3.60 90.00
brawn 2.50 56.00
greaves 2.40 45.00
welt 3.50 63.38
</pre>
</pre>


Line 3,033: Line 2,974:
Take 3.50 of the welt (for 63.38)
Take 3.50 of the welt (for 63.38)
For a grand total of: 349.38</pre>
For a grand total of: 349.38</pre>

=={{header|Raku}}==
(formerly Perl 6)
{{works with|rakudo|2015-09-16}}
This Solutions sorts the item by WEIGHT/VALUE
<lang perl6>class KnapsackItem {
has $.name;
has $.weight is rw;
has $.price is rw;
has $.ppw;

method new (Str $n, Rat $w, Int $p) {
self.bless(:name($n), :weight($w), :price($p), :ppw($w/$p))
}

method cut-maybe ($max-weight) {
return False if $max-weight > $.weight;
$.price = $max-weight / $.ppw;
$.weight = $.ppw * $.price;
return True;
}

method gist () { sprintf "%8s %1.2f %3.2f",
$.name,
$.weight,
$.price }
}

my $max-w = 15;
say "Item Portion Value";

.say for gather
for < 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 >
==> map({ KnapsackItem.new($^a, $^b, $^c) })
==> sort *.ppw
{
my $last-one = .cut-maybe($max-w);
take $_;
$max-w -= .weight;
last if $last-one;
}</lang>
'''Output:'''
<pre>
%perl6 knapsack_continous.p6
Item Portion Value
salami 3.00 95.00
ham 3.60 90.00
brawn 2.50 56.00
greaves 2.40 45.00
welt 3.50 63.38
</pre>


=={{header|REXX}}==
=={{header|REXX}}==
Line 3,210: Line 3,210:
-----------------------
-----------------------
total 15.000 349.378</pre>
total 15.000 349.378</pre>



=={{header|Ruby}}==
=={{header|Ruby}}==
Line 3,403: Line 3,402:
salami 3.0
salami 3.0
welt 3.5 </pre>
welt 3.5 </pre>

=={{header|Scala}}==
=={{header|Scala}}==
===Functional approach (Tail recursive)===
===Functional approach (Tail recursive)===
Line 3,470: Line 3,470:
Totals: weight: 15.0, value: 349.38</pre>
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)]-->.
{{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}}==
=={{header|Sidef}}==
{{trans|Perl}}
{{trans|Perl}}
Retrieved from "https://rosettacode.org/wiki/Knapsack_problem/Continuous"