Knapsack problem/Bounded: Difference between revisions
→{{header|Phix}}
m (→{{header|C++}}) |
|||
Line 2,261:
=={{header|Phix}}==
===Very dumb and very slow brute force version===
Of no practical use, except for comparison against improvements.
<lang Phix>atom t0 = time()
constant goodies = {
-- item weight value pieces
{"map", 9, 150, 1},
{"compass", 13, 35, 1},
{"sandwich", 50, 60, 2},
{"glucose", 15, 60, 2},
{"tin", 68, 45, 3},
{"banana", 27, 60, 3},
{"apple", 39, 40, 3},
{"cheese", 23, 30, 1},
{"beer", 52, 10, 3},
{"suntan cream", 11, 70, 1},
{"water", 153, 200, 2},
{"camera", 32, 30, 1},
{"T-shirt", 24, 15, 2},
{"trousers", 48, 10, 2},
{"umbrella", 73, 40, 1},
{"waterproof trousers", 42, 70, 1},
{"waterproof overclothes", 43, 75, 1},
{"note-case", 22, 80, 1},
{"sunglasses", 7, 20, 1},
{"towel", 18, 12, 2},
{"socks", 4, 50, 1},
{"book", 30, 10, 2}}
function knapsack(integer max_weight, integer at)
integer best_points = 0, points
sequence best_choices = {}, choices
atom act_weight = 0, sub_weight
if at>=1 then
integer {?,witem,pitem,imax} = goodies[at]
for i=0 to imax do
integer wlim = max_weight-i*witem
if wlim<0 then exit end if
{points,sub_weight,choices} = knapsack(wlim, at-1)
points += i*pitem
if points>best_points then
best_points = points
best_choices = choices&i
act_weight = sub_weight+i*witem
end if
end for
end if
return {best_points, act_weight, best_choices}
end function
sequence res = knapsack(400, length(goodies)) -- {points,act_weight,choices}
atom weight = 0, witem
atom points = 0, pitem
string idesc
for i=1 to length(goodies) do
integer c = res[3][i]
if c then
{idesc,witem,pitem} = goodies[i]
printf(1,"%d %s\n",{c,idesc})
weight += c*witem
points += c*pitem
end if
end for
if points!=res[1] then ?9/0 end if -- sanity check
printf(1,"Value %d, weight %g [%3.2fs]\n",{points,weight,time()-t0})</lang>
{{out}}
<pre>
1 map
1 compass
2 glucose
3 banana
1 cheese
1 suntan cream
1 water
1 waterproof overclothes
1 note-case
1 sunglasses
1 socks
Value 1010, weight 396 [17.53s]
</pre>
===Dynamic Programming version===
Much faster but limited to integer weights
{{trans|C}}
<lang Phix>sequence items = {
{"map", 9, 150, 1},
{"compass", 13, 35, 1},
{"water", 153, 200, 2},
{"sandwich", 50, 60, 2},
{"glucose", 15, 60, 2},
{"tin", 68, 45, 3},
{"banana", 27, 60, 3},
{"apple", 39, 40, 3},
{"cheese", 23, 30, 1},
{"beer", 52, 10, 3},
{"suntan cream", 11, 70, 1},
{"camera", 32, 30, 1},
{"T-shirt", 24, 15, 2},
{"trousers", 48, 10, 2},
{"umbrella", 73, 40, 1},
{"waterproof trousers", 42, 70, 1},
{"waterproof overclothes",43, 75, 1},
{"note-case", 22, 80, 1},
{"sunglasses", 7, 20, 1},
{"towel", 18, 12, 2},
{"socks", 4, 50, 1},
{"book", 30, 10, 2},
};
sequence {names,weights,points,counts} = columnize(items)
constant n = length(items)
function knapsack(int w)
int v
-- m is the achievable points matrix:
-- Note that Phix uses 1-based indexes, so m[1][1]
-- actually holds points for 0 items of weight 0,
-- and m[n+1][w+1] is for n items at weight w.
seq m = repeat(repeat(0,w+1),n+1)
for i=1 to n do
for j=1 to w+1 do -- (0 to w really)
m[i+1][j] = m[i][j]
for k=1 to counts[i] do
if k*weights[i]>j-1 then
exit
end if
v = m[i][j-k*weights[i]]+k*points[i]
if v>m[i+1][j] then
m[i+1][j] = v
end if
end for
end for
end for
seq s = repeat(0,n)
int j = w+1 -- (w -> 0 really)
for i=n+1 to 2 by -1 do -- (n to 1 really)
v = m[i][j]
int k = 0
while v!=m[i-1][j]+k*points[i-1] do
s[i-1] += 1
j -= weights[i-1]
k += 1
end while
end for
return s
end function
int tc = 0, tw = 0, tv = 0
seq s = knapsack(400)
for i=1 to n do
int si = s[i]
if si then
printf(1,"%-22s %5d %5d %5d\n", {names[i], si, si*weights[i], si*points[i]})
tc += si
tw += si*weights[i]
tv += si*points[i]
end if
end for
printf(1,"%-22s %5d %5d %5d\n", {"count, weight, points:", tc, tw, tv})</lang>
{{out}}
<pre>
map 1 9 150
compass 1 13 35
water 1 153 200
glucose 2 30 120
banana 3 81 180
cheese 1 23 30
suntan cream 1 11 70
waterproof overclothes 1 43 75
note-case 1 22 80
sunglasses 1 7 20
socks 1 4 50
count, weight, points: 14 396 1010
</pre>
===Range cache version===
The main problem with the dynamic programming solution is that it is only practical for integer weights. You could
multiply by 1000 and truncate to get an approximation to the nearest 0.001kg, but the memory use
would obviously increase dramatically. A naive cache could also suffer similarly, if it retained
duplicate solutions for w=15.783, 15.784, 15.785, and everything in between.
Using a (bespoke) range cache solves this problem.
<lang Phix>--
-- demo\rosetta\knapsackB.exw
-- ==========================
--
atom
enum HI,PTS,ACTW,SOLN
sequence range_cache = {}
integer
procedure add_range(integer at, atom weight, atom actual_weight, atom points, sequence soln)
if actual_weight>weight then ?9/0 end if
for i=length(range_cache)+1 to at do -- (while too small do)
range_cache = append(range_cache,{{weight,points,actual_weight,soln}})
cache_entries += 1
return
end if
end for
for i=1 to length(range_cache[at]) do
sequence rcati =
if weight=rcati[ACTW] then
if rcati[PTS..SOLN]!={points,actual_weight,soln} then ?9/0 end if
elsif weight<rcati[ACTW] then
-- (we cannot extend an existing range down...)
if soln=rcati[SOLN] then ?9/0 end if
-- insert a new range
range_cache[at][i..i-1] = {{weight,points,actual_weight,soln}}
cache_entries += 1
return
elsif soln=rcati[SOLN] then
if rcati[PTS..SOLN]!={points,actual_weight,soln} then ?9/0 end if
if weight>rcati[HI] then -- extend existing range up
rcati = {}
range_cache[at][i][HI] = weight
end if
return
elsif weight<=rcati[HI] then
?9/0 -- duplicate solution?? (or discard as below)
-- return -- (discard)
end if
range_cache[at] = append(range_cache[at],{weight,points,actual_weight,soln})
cache_entries
end procedure
function in_range(integer at, atom weight)
if at<=length(range_cache) then
for i=1 to length(range_cache[at])
if weight>=rcati[ACTW] then
return rcati[PTS..SOLN] -- {pts,act_weight,soln}
end if
exit
end if
end for
end if
return
end function
constant goodies = {
-- item weight value pieces
{"map",
{"compass",
{"sandwich",
{"glucose",
{"tin",
{"banana",
{"apple",
{"cheese",
{"beer",
{"suntan cream",
{"water",
{"camera",
{"T-shirt",
{"trousers",
{"umbrella",
{"waterproof trousers",
{"waterproof overclothes",
{"note-case",
{"sunglasses",
{"towel",
{"socks",
{"book",
integer cache_hits = 0
integer cache_misses = 0
function knapsack(integer max_weight, integer at)
integer best_points = 0, points
sequence best_choices
atom act_weight = 0, sub_weight
if at>=1 then
sequence soln = in_range(at,max_weight)
if length(soln) then
cache_hits += 1
return soln
end if
cache_misses += 1
integer {?,witem,pitem,imax} = goodies[at]
for i=0 to imax do
integer wlim = max_weight-i*witem
if wlim<0 then exit end if
{points,sub_weight,choices} = knapsack(wlim, at-1)
points += i*pitem
if points>best_points then
best_points = points
best_choices = choices&i
act_weight = sub_weight+i*witem
end if
end for
add_range(at,max_weight,act_weight,best_points,best_choices)
end if
return {best_points, act_weight, best_choices}
end function
sequence res = knapsack(400, length(goodies)) -- {points,act_weight,choices}
atom weight = 0, witem
atom points = 0, pitem
string idesc
for i=1 to length(goodies) do
integer c = res[3][i]
if c then
printf(1,"%d %s\n",{c,idesc})
weight += c*witem
points += c*pitem
end if
end for
if points!=res[1] then ?9/0 end if -- sanity check
printf(1,"Value %d, weight %g [%3.2fs]\n",{points,weight,time()-t0})
printf(1,"cache_entries:%d, hits:%d, misses:%d\n",{cache_entries,cache_hits,cache_misses})</lang>
{{out}}
<pre>
1 map
1 compass
2 glucose
3 banana
1 cheese
1 suntan cream
1 water
1 waterproof overclothes
1 note-case
1 sunglasses
1 socks
Value 1010, weight 396 [0.00s]
cache_entries:409, hits:1226, misses:882
</pre>
The distributed version contains additional comments and extra code for comparing this against a naive cache and no cache (CACHE_RANGE shown above).<br>
CACHE_SIMPLE: (as above but ending)
<pre>
Value 1010, weight 396 [0.08s]
cache_entries:5549, hits:7707, misses:5549
</pre>
Even on this simple integer-only case, range cache reduces cache size better than 10-fold and effort 6-fold.<br>
Anf finally CACHE_NONE (the dumb version): (as above but ending)
<pre>
Value 1010, weight 396 [
cache_entries:0, hits:0, misses:33615741
</pre>
| |||