algorithm - How to code a dynamic solution for the 0/1 Knapsack with a specific number of each item -
is possible code dynamic solution 1/0 knapsack problem has requirement number of each item?
for example knapsack requires:
1 of item_one
2 of item_two
3 of item_three
1 of item_four
1 of item_five
1 of item_six
each item has weight , there max weight of 60000 in sense normal knapsack problem.
beyond difference im trying minimize value instead of maximize.
here brute force code in vba im running on hunderes of items need faster solution. help!
function knapsacksolver(item_one, item_two, item_three, item_four, item_five, item_six) dim knapsack variant redim knapsack(1 9, 1 5) variant dim value long dim minvalue long dim cap long dim weight long minvalue = 9999999 weight = 0 cap = 60000 = 1 ubound(item_one) j = 1 ubound(item_two) t = 1 ubound(item_two) if j <> t m = 1 ubound(item_three) n = 1 ubound(item_three) if n <> m p = 1 ubound(item_three) if n <> p q = 1 ubound(item_four) r = 1 ubound(item_five) s = 1 ubound(item_six) weight = item_one(i, 3) + item_two(j, 3) + item_two(t, 3) + item_three(m, 3) + item_three(n, 3) + item_three(p, 3) + item_four(q, 3) + item_five(r, 3) + item_six(s, 3) value = item_one(i, 4) + item_two(j, 4) + item_two(t, 4) + item_three(m, 4) + item_three(n, 4) + item_three(p, 4) + item_four(q, 4) + item_five(r, 4) + item_six(s, 4) if value < minvalue , weight < cap minvalue = value 'adding attribute each item array' knapsack(1, 1) = item_one(i, 1) knapsack(1, 2) = item_one(i, 2) knapsack(1, 3) = item_one(i, 3) knapsack(1, 4) = item_one(i, 4) knapsack(1, 5) = item_one(i, 5) knapsack(2, 1) = item_two(j, 1) knapsack(2, 2) = item_two(j, 2) knapsack(2, 3) = item_two(j, 3) knapsack(2, 4) = item_two(j, 4) knapsack(2, 5) = item_two(j, 5) knapsack(3, 1) = item_two(t, 1) knapsack(3, 2) = item_two(t, 2) knapsack(3, 3) = item_two(t, 3) knapsack(3, 4) = item_two(t, 4) knapsack(3, 5) = item_two(t, 5) knapsack(4, 1) = item_three(m, 1) knapsack(4, 2) = item_three(m, 2) knapsack(4, 3) = item_three(m, 3) knapsack(4, 4) = item_three(m, 4) knapsack(4, 5) = item_three(m, 5) knapsack(5, 1) = item_three(n, 1) knapsack(5, 2) = item_three(n, 2) knapsack(5, 3) = item_three(n, 3) knapsack(5, 4) = item_three(n, 4) knapsack(5, 5) = item_three(n, 5) knapsack(6, 1) = item_three(p, 1) knapsack(6, 2) = item_three(p, 2) knapsack(6, 3) = item_three(p, 3) knapsack(6, 4) = item_three(p, 4) knapsack(6, 5) = item_three(p, 5) knapsack(7, 1) = item_four(q, 1) knapsack(7, 2) = item_four(q, 2) knapsack(7, 3) = item_four(q, 3) knapsack(7, 4) = item_four(q, 4) knapsack(7, 5) = item_four(q, 5) knapsack(8, 1) = item_five(r, 1) knapsack(8, 2) = item_five(r, 2) knapsack(8, 3) = item_five(r, 3) knapsack(8, 4) = item_five(r, 4) knapsack(8, 5) = item_five(r, 5) knapsack(9, 1) = item_six(s, 1) knapsack(9, 2) = item_six(s, 2) knapsack(9, 3) = item_six(s, 3) knapsack(9, 4) = item_six(s, 4) knapsack(9, 5) = item_six(s, 5) end if weight = 0 next s next r next q end if next p end if next n next m end if next t next j next knapsacksolver = knapsack end function
Comments
Post a Comment