Anonymous user
Knapsack problem/Continuous: Difference between revisions
→{{header|Julia}}
(→{{header|Kotlin}}: Updated example see https://github.com/dkandalov/rosettacode-kotlin for details) |
|||
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.
'''Type and Functions''':
<lang julia>struct KPCSupply{T<:Real}
▲ item::S
weight::T
value::T
uvalue::T
end
Base.isless(a::KPCSupply, b::KPCSupply) = a.uvalue<b.uvalue▼
w, v = promote(weight, value)
▲function KPCSupply{S<:String, T<:Real}(item::S, weight::T, value::T)
▲ KPCSupply(item, weight, value, value/weight)
end
Base.show(io::IO, s::KPCSupply) = print(io, s.item, @sprintf " (%.2f kg, %.2f €, %.2f €/kg)" s.weight s.value s.uvalue)
▲Base.isless(a::KPCSupply, b::KPCSupply) = a.uvalue < b.uvalue
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)
for s in sort(store, rev = true)
if kweight + s.weight
kweight += s.weight
push!(
else
w = capacity - kweight
v = w * s.uvalue
push!(
break
end
end
return
end</lang>
'''Main''':
<lang julia>store = [KPCSupply("beef", 38//10, 36),
KPCSupply("
KPCSupply("
KPCSupply("
KPCSupply("
KPCSupply("
KPCSupply("
KPCSupply("
sack = solve(store, 15
println("The store contains:\n - ", join(store, "\n - "))▼
@printf("\nTotal value in the sack: %.2f €\n", sum(getfield.(sack, :value)))</lang>
{{out}}▼
▲println("The store contains:")
<pre>The store contains:▼
- beef (3.80 kg, 36.00 €, 9.47 €/kg)
- pork (5.40 kg, 43.00 €, 7.96 €/kg)
- ham (3.60 kg, 90.00 €, 25.00 €/kg)
- 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)
The thief should take::▼
- salami (3.00 kg, 95.00 €, 31.67 €/kg)
▲println("The thief should take:")
- ham (3.60 kg, 90.00 €, 25.00 €/kg)
- brawn (2.50 kg, 56.00 €, 22.40 €/kg)
- greaves (2.40 kg, 45.00 €, 18.75 €/kg)
- welt (3.50 kg, 63.38 €, 67.00 €/kg)
▲{{out}}
▲The store contains:
▲ greaves 2.4 18.75
▲ salami 3.0 31.67
▲ sausage 5.9 16.61
Total value in the sack: 349.38 €</pre>
▲The thief should take:
=={{header|Kotlin}}==
| |||