Knapsack problem/Continuous: Difference between revisions

Content added Content deleted
(→‎{{header|Kotlin}}: Updated example see https://github.com/dkandalov/rosettacode-kotlin for details)
Line 1,777: Line 1,777:
An [http://docs.julialang.org/en/release-0.3/manual/constructors/#outer-constructor-methods outer constructor method] is used to create instances of <code>KPCSupply</code> when only the <code>item</code>, <code>weight</code> and <code>value</code> are supplied. The <code>isless</code> method is provided for <code>KPCSupply</code> objects so that items are transparently sorted by their unit value. <code>KPCSupply</code> supports any real type for <code>weight</code>, <code>value</code> and <code>uvalue</code> (though this simple implementation does not support mixed types or promotion). This solution uses [http://docs.julialang.org/en/release-0.3/manual/complex-and-rational-numbers/#rational-numbers Rational] numbers to avoid rounding errors until the results are printed.
An [http://docs.julialang.org/en/release-0.3/manual/constructors/#outer-constructor-methods outer constructor method] is used to create instances of <code>KPCSupply</code> when only the <code>item</code>, <code>weight</code> and <code>value</code> are supplied. The <code>isless</code> method is provided for <code>KPCSupply</code> objects so that items are transparently sorted by their unit value. <code>KPCSupply</code> supports any real type for <code>weight</code>, <code>value</code> and <code>uvalue</code> (though this simple implementation does not support mixed types or promotion). This solution uses [http://docs.julialang.org/en/release-0.3/manual/complex-and-rational-numbers/#rational-numbers Rational] numbers to avoid rounding errors until the results are printed.


'''Type and Functions'''
'''Type and Functions''':
<lang julia>struct KPCSupply{T<:Real}
<lang Julia>
⚫
item::String
immutable KPCSupply{S<:String, T<:Real}
⚫
item::S
weight::T
weight::T
value::T
value::T
uvalue::T
uvalue::T
end
end
⚫
function KPCSupply(item::AbstractString, weight::Real, value::Real)
⚫
Base.isless(a::KPCSupply, b::KPCSupply) = a.uvalue<b.uvalue
w, v = promote(weight, value)

⚫
KPCSupply(item, w, v, v / w)
⚫
function KPCSupply{S<:String, T<:Real}(item::S, weight::T, value::T)
⚫
KPCSupply(item, weight, value, value/weight)
end
end


Base.show(io::IO, s::KPCSupply) = print(io, s.item, @sprintf " (%.2f kg, %.2f €, %.2f €/kg)" s.weight s.value s.uvalue)
function solve{S<:String, T<:Real}(store::Array{KPCSupply{S,T},1},
⚫
Base.isless(a::KPCSupply, b::KPCSupply) = a.uvalue < b.uvalue
capacity::T)

ksack = KPCSupply{S,T}[]
function solve(store::Vector{KPCSupply{T}}, capacity::Real) where T<:Real
sack = similar(store, 0) # vector like store, but of length 0
kweight = zero(T)
kweight = zero(T)
for s in sort(store, rev=true)
for s in sort(store, rev = true)
if kweight + s.weight <= capacity
if kweight + s.weight ≤ capacity
kweight += s.weight
kweight += s.weight
push!(ksack, s)
push!(sack, s)
else
else
w = capacity-kweight
w = capacity - kweight
v = w*s.uvalue
v = w * s.uvalue
push!(ksack, KPCSupply(s.item, w, v, s.uvalue))
push!(sack, KPCSupply(s.item, w, v, s.value))
break
break
end
end
end
end
return ksack
return sack
end
end</lang>
</lang>


'''Main'''
'''Main''':
<lang julia>store = [KPCSupply("beef", 38//10, 36),
<lang Julia>
store = [KPCSupply("beef", 38//10, 36//1),
KPCSupply("pork", 54//10, 43),
KPCSupply("pork", 54//10, 43//1),
KPCSupply("ham", 36//10, 90),
KPCSupply("ham", 36//10, 90//1),
KPCSupply("greaves", 24//10, 45),
KPCSupply("greaves", 24//10, 45//1),
KPCSupply("flitch", 4//1, 30),
KPCSupply("flitch", 4//1, 30//1),
KPCSupply("brawn", 25//10, 56),
KPCSupply("brawn", 25//10, 56//1),
KPCSupply("welt", 37//10, 67),
KPCSupply("welt", 37//10, 67//1),
KPCSupply("salami", 3//1, 95),
KPCSupply("salami", 3//1, 95//1),
KPCSupply("sausage", 59//10, 98)]
KPCSupply("sausage", 59//10, 98//1)]


sack = solve(store, 15//1)
sack = solve(store, 15)
⚫
println("The store contains:\n - ", join(store, "\n - "))
⚫
println("\nThe thief should take::\n - ", join(sack, "\n - "))
@printf("\nTotal value in the sack: %.2f €\n", sum(getfield.(sack, :value)))</lang>


⚫
{{out}}
⚫
println("The store contains:")
⚫
<pre>The store contains:
println(" Item Weight Unit Price")
- beef (3.80 kg, 36.00 €, 9.47 €/kg)
for s in store
- pork (5.40 kg, 43.00 €, 7.96 €/kg)
println(@sprintf("%12s %4.1f %6.2f",
- ham (3.60 kg, 90.00 €, 25.00 €/kg)
s.item, float(s.weight), float(s.uvalue)))
⚫
- greaves (2.40 kg, 45.00 €, 18.75 €/kg)
end
- flitch (4.00 kg, 30.00 €, 7.50 €/kg)
- brawn (2.50 kg, 56.00 €, 22.40 €/kg)
- welt (3.70 kg, 67.00 €, 18.11 €/kg)
⚫
- salami (3.00 kg, 95.00 €, 31.67 €/kg)
⚫
- sausage (5.90 kg, 98.00 €, 16.61 €/kg)


⚫
The thief should take::
println()
- salami (3.00 kg, 95.00 €, 31.67 €/kg)
⚫
println("The thief should take:")
- ham (3.60 kg, 90.00 €, 25.00 €/kg)
println(" Item Weight Value")
- brawn (2.50 kg, 56.00 €, 22.40 €/kg)
for s in sack
- greaves (2.40 kg, 45.00 €, 18.75 €/kg)
println(@sprintf("%12s %4.1f %6.2f",
- welt (3.50 kg, 63.38 €, 67.00 €/kg)
s.item, float(s.weight), float(s.value)))
end
w = mapreduce(x->x.weight, +, sack)
v = mapreduce(x->x.value, +, sack)
println(@sprintf("%12s %4.1f %6.2f",
"Total", float(w), float(v)))
</lang>

⚫
{{out}}
<pre>
⚫
The store contains:
Item Weight Unit Price
beef 3.8 9.47
pork 5.4 7.96
ham 3.6 25.00
⚫
greaves 2.4 18.75
flitch 4.0 7.50
brawn 2.5 22.40
welt 3.7 18.11
⚫
salami 3.0 31.67
⚫
sausage 5.9 16.61


Total value in the sack: 349.38 €</pre>
⚫
The thief should take:
Item Weight Value
salami 3.0 95.00
ham 3.6 90.00
brawn 2.5 56.00
greaves 2.4 45.00
welt 3.5 63.38
Total 15.0 349.38
</pre>


=={{header|Kotlin}}==
=={{header|Kotlin}}==
Retrieved from "https://rosettacode.org/wiki/Knapsack_problem/Continuous"