OpenEuphoria

Re: rosettacode 500 milestone passed

• Posted by petelomax Mar 19, 2017
• 1625 views

I translated the C dynamic programming version:

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}) 

Simple and elegant, yet quite difficult to get your head around - there are some youtube vids (search for knapsack problem) that might help.

Pete