Anonymous user
Knapsack problem/Continuous: Difference between revisions
→{{header|Julia}}: A new entry for Julia
(→{{header|XPL0}}: Added zkl) |
(→{{header|Julia}}: A new entry for Julia) |
||
Line 1,456:
Total value: 349.3783783783784
Total weight: 15</lang>
=={{header|Julia}}==
This solution is built around the immutable type <code>KPCSupply</code>, which holds an item's data including its unit value (<code>uvalue</code>). When the store's inventory is kept in this way, the solution to the continuous knapsack problem (provided by <code>solve</code>), is straightforward. The thief should pack as much of the highest value items as are available until full capacity is reached, topping off with as much of the last item as the knapsack will hold. (If the store contains less than the thief's knapsack will hold, he'll take the store's entire inventory.)
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>
immutable KPCSupply{S<:String, T<:Real}
item::S
weight::T
value::T
uvalue::T
end
Base.isless(a::KPCSupply, b::KPCSupply) = a.uvalue<b.uvalue
function KPCSupply{S<:String, T<:Real}(item::S, weight::T, value::T)
KPCSupply(item, weight, value, value/weight)
end
function solve{S<:String, T<:Real}(store::Array{KPCSupply{S,T},1},
capacity::T)
ksack = KPCSupply{S,T}[]
kweight = zero(T)
for s in sort(store, rev=true)
if kweight + s.weight <= capacity
kweight += s.weight
push!(ksack, s)
else
w = capacity-kweight
v = w*s.uvalue
push!(ksack, KPCSupply(s.item, w, v, s.uvalue))
break
end
end
return ksack
end
</lang>
'''Main'''
<lang Julia>
store = [KPCSupply("beef", 38//10, 36//1),
KPCSupply("pork", 54//10, 43//1),
KPCSupply("ham", 36//10, 90//1),
KPCSupply("greaves", 24//10, 45//1),
KPCSupply("flitch", 4//1, 30//1),
KPCSupply("brawn", 25//10, 56//1),
KPCSupply("welt", 37//10, 67//1),
KPCSupply("salami", 3//1, 95//1),
KPCSupply("sausage", 59//10, 98//1)]
sack = solve(store, 15//1)
println("The store contains:")
println(" Item Weight Unit Price")
for s in store
println(@sprintf("%12s %4.1f %6.2f",
s.item, float(s.weight), float(s.uvalue)))
end
println()
println("The thief should take:")
println(" Item Weight Value")
for s in sack
println(@sprintf("%12s %4.1f %6.2f",
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
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|Mathematica}}==
| |||