Knapsack problem/Continuous: Difference between revisions

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