CODEWITHSUNDEEP
algorithmknapsack-problem
skyjlv
skyjlv

Reputation: 17

0/1 Knapsack Clarification and Optimization

I was reading wikipedia regarding the 0-1 knapsack problem. I just want to clarify a couple things. I have two questions: http://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_Knapsack_Problem

I encountered this pseudo-code:

// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
for w from 0 to W do
  m[0, w] := 0
end for 
for i from 1 to n do
  for j from 0 to W do
    if j >= w[i] then
      m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])
    else
      m[i, j] := m[i-1, j]
    end if
  end for
end for

Specifically for this part:

    if j >= w[i] then
      m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])

1) Correct me if I'm wrong, but shouldn't it be:

      m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i], m[i,j-w[i]] + v[i])

?

Or if not, can someone explain me why it's not needed?

...

2) And I also have another question, if say I want to optimize this a bit. Would it be wise to have the loop "for j from 0 to W" increment by the GCD of all the weights of the items (i.e. GCD of the values stored in array w). (I'm thinking just code-wise right now when I'm about to implement it).

Upvotes: 0

Views: 807

Answers (1)

i Code 4 Food
i Code 4 Food

Reputation: 2154

1) When you add m[i,j-w[i]] + v[i], you're allowing the same item i to be selected more than once, thus it is no longer 0/1 Knapsack - it becomes a Knapsack problem with unlimited amounts of each item.

2) Yes, but this GCD usually comes down to 1 on real instances, thus not worth bothering with for general cases, unless you know beforehand that your data would benefit from it. (In this case, you'd actually want to divide all your data by the GCD, and keep the original algorithm incrementing 1 at a time, then multiply the final result by the GCD. This would save you memory as well, but your Knapsack capacity must also be divisible by such GCD)

Upvotes: 1

Related Questions