Knapsack problem/Bounded: Difference between revisions
Content added Content deleted
m (→{{header|C++}}) |
|||
Line 2,261: | Line 2,261: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
===Very dumb and very slow brute force version=== |
|||
{{incorrect|Phix|counterexample found, will redo [[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 06:17, 19 March 2017 (UTC)}} |
|||
Of no practical use, except for comparison against improvements. |
|||
There is a potential optimisation here that I will discuss on the talk page, but for now I have left the |
|||
<lang Phix>atom t0 = time() |
|||
"and not terminate" commented out, along with a ?9/0 to crash if a disproving dataset is found. |
|||
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>-- |
<lang Phix>-- |
||
-- demo\rosetta\knapsackB.exw |
-- demo\rosetta\knapsackB.exw |
||
-- ========================== |
-- ========================== |
||
-- |
-- |
||
atom |
atom t0 = time() |
||
enum HI,PTS,ACTW,SOLN |
|||
integer terminate=0 |
|||
sequence range_cache = {} |
|||
integer |
integer cache_entries = 0 |
||
function knapsack(sequence res, goodies, atom points, weight, at=1, sequence chosen={}) |
|||
procedure add_range(integer at, atom weight, atom actual_weight, atom points, sequence soln) |
|||
atom {witem,pitem,mitem} = goodies[at][2] |
|||
if actual_weight>weight then ?9/0 end if |
|||
integer n = min(floor(weight/witem),mitem) |
|||
for i=length(range_cache)+1 to at do -- (while too small do) |
|||
chosen &= n |
|||
if i=at then |
|||
range_cache = append(range_cache,{{weight,points,actual_weight,soln}}) |
|||
weight -= n*witem -- decrease weight left |
|||
cache_entries += 1 |
|||
if at=length(goodies) then |
|||
return |
|||
if time()>t1 or points=1010 then |
|||
?{points,weight,chosen} |
|||
t1 = time()+1 |
|||
end if |
|||
attempts += 1 |
|||
if length(res)=0 |
|||
or res<{points,weight} then |
|||
if terminate then |
|||
?9/0 |
|||
end if |
|||
res = {points,weight,chosen} |
|||
end if |
end if |
||
range_cache = append(range_cache,{}) |
|||
end for |
|||
?"terminate" |
|||
for i=1 to length(range_cache[at]) do |
|||
?res |
|||
sequence rcati = range_cache[at][i] |
|||
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 |
end if |
||
end for |
|||
range_cache[at] = append(range_cache[at],{weight,points,actual_weight,soln}) |
|||
-- proposed optimisation: |
|||
cache_entries += 1 |
|||
end procedure |
|||
-- while n>=0 and not terminate do |
|||
res = knapsack(res,goodies,points,weight,at+1,chosen) |
|||
function in_range(integer at, atom weight) |
|||
n -= 1 |
|||
if at<=length(range_cache) then |
|||
chosen[$] = n |
|||
for i=1 to length(range_cache[at]) do |
|||
sequence rcati = range_cache[at][i] |
|||
if weight<=rcati[HI] then |
|||
if weight>=rcati[ACTW] then |
|||
return rcati[PTS..SOLN] -- {pts,act_weight,soln} |
|||
end if |
|||
exit |
|||
end if |
|||
end for |
|||
end if |
end if |
||
return |
return {} -- (no suitable cache entry found) |
||
end function |
end function |
||
constant goodies = { |
|||
function byweightedvalue(object a, b) |
|||
-- sort by weight/value |
|||
return compare(a[2][1]/a[2][2],b[2][1]/b[2][2]) |
|||
-- nb other sort orders break the optimisation |
|||
end function |
|||
function cap(sequence s) |
|||
-- cap the last entry to something that will fit |
|||
-- (it would be perfectly valid to cap all entries, |
|||
-- but only the last one will make any difference.) |
|||
integer {witem,?,mitem} = s[$][2] |
|||
s[$][2][3] = min(floor(400/witem),mitem) |
|||
return s |
|||
end function |
|||
constant goodies = cap(custom_sort(routine_id("byweightedvalue"),{ |
|||
-- item weight value pieces |
-- item weight value pieces |
||
{"map", |
{"map", 9, 150, 1}, |
||
{"compass", |
{"compass", 13, 35, 1}, |
||
{"sandwich", |
{"sandwich", 50, 60, 2}, |
||
{"glucose", |
{"glucose", 15, 60, 2}, |
||
{"tin", |
{"tin", 68, 45, 3}, |
||
{"banana", |
{"banana", 27, 60, 3}, |
||
{"apple", |
{"apple", 39, 40, 3}, |
||
{"cheese", |
{"cheese", 23, 30, 1}, |
||
{"beer", |
{"beer", 52, 10, 3}, |
||
{"suntan cream", |
{"suntan cream", 11, 70, 1}, |
||
{"water", |
{"water", 153, 200, 2}, |
||
{"camera", |
{"camera", 32, 30, 1}, |
||
{"T-shirt", |
{"T-shirt", 24, 15, 2}, |
||
{"trousers", |
{"trousers", 48, 10, 2}, |
||
{"umbrella", |
{"umbrella", 73, 40, 1}, |
||
{"waterproof trousers", |
{"waterproof trousers", 42, 70, 1}, |
||
{"waterproof overclothes", |
{"waterproof overclothes", 43, 75, 1}, |
||
{"note-case", |
{"note-case", 22, 80, 1}, |
||
{"sunglasses", |
{"sunglasses", 7, 20, 1}, |
||
{"towel", |
{"towel", 18, 12, 2}, |
||
{"socks", |
{"socks", 4, 50, 1}, |
||
{"book", |
{"book", 30, 10, 2}} |
||
integer cache_hits = 0 |
|||
atom t0 = time() |
|||
integer cache_misses = 0 |
|||
-- res is {points,(weight left),{counts}} |
|||
sequence res = knapsack({},goodies,0,400) |
|||
function knapsack(integer max_weight, integer at) |
|||
sequence counts = res[3] |
|||
integer best_points = 0, points |
|||
sequence {d,wv} = columnize(goodies), |
|||
sequence best_choices = {}, choices |
|||
atom act_weight = 0, sub_weight |
|||
atom weight = sum(sq_mul(counts,w)) |
|||
if at>=1 then |
|||
printf(1,"Value %d, weight %g [%d attempts, %3.2fs]:\n",{res[1],weight,attempts,time()-t0}) |
|||
sequence soln = in_range(at,max_weight) |
|||
for i=1 to length(counts) do |
|||
if length(soln) then |
|||
integer c = counts[i] |
|||
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 |
if c then |
||
{idesc,witem,pitem} = goodies[i] |
|||
printf(1,"%d %s\n",{c,idesc}) |
|||
weight += c*witem |
|||
points += c*pitem |
|||
end if |
end if |
||
end for |
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}} |
{{out}} |
||
<pre> |
<pre> |
||
Value 1010, weight 396 [17155053 attempts, 14.83s]: |
|||
1 map |
1 map |
||
1 socks |
|||
1 suntan cream |
|||
2 glucose |
|||
1 note-case |
|||
1 sunglasses |
|||
1 compass |
1 compass |
||
2 glucose |
|||
3 banana |
3 banana |
||
1 waterproof overclothes |
|||
1 water |
|||
1 cheese |
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> |
</pre> |
||
Even on this simple integer-only case, range cache reduces cache size better than 10-fold and effort 6-fold.<br> |
|||
with proposed optimisation: |
|||
Anf finally CACHE_NONE (the dumb version): (as above but ending) |
|||
<pre> |
<pre> |
||
Value 1010, weight 396 [ |
Value 1010, weight 396 [18.14s] |
||
cache_entries:0, hits:0, misses:33615741 |
|||
(plus same as above) |
|||
</pre> |
</pre> |
||