Brute force implementation for 0-1 Knapsack

Question

I'm struggling with the given task for almost a week without success of finding solution so this site is my last hope.

I have 0-1 Knapsack problem which has 20 items with different values and weights, maximum weight of sack is 524. Now i need to implement brute force to find optimal solution subset of 20 items so that total weights <= 524 and maximum values of chosen items.

Could you please point me out or better give detailed implementation to analyze how it work!! Thank you very much

yes this is homework and i'm stuck at how to find all possible combinations, should i store combinations to array? — MinhHoang

Patrick87 Patrick87 · Accepted Answer · 2011-10-31T14:08:34

The brute-force idea is easy:

Generate all possible subsets of your 20 items, saving only those which satisfy your weight constraint. If you want to be fancy, you can even only consider subsets to which you cannot add anything else without violating the weight constraint, since only these can possibly be the right answer. O(2^n)
Find the subset with maximum weight. linear in terms of the number of candidates, and since we have O(2^n) candidates, this is O(2^n).

Please comment if you'd like some pseudocode.

EDIT: What the hey, here's the pseudocode just in case.

  GetCandidateSubsets(items[1..N], buffer, maxw)
  1. addedSomething = false
  2. for i = 1 to N do
  3.    if not buffer.contains(item[i]) and
           weight(buffer) + weight(items[i]) <= maxw then
  4.       add items[i] to buffer
  5.       GetCandidateSubsets(items[1..N], buffer)
  6.       remove items[i] from buffer
  7.       addedSomething = true
  8. if not addedSomething then
  9.    emit & store buffer

Note that the GetCandidateSubsets function is not very efficient, even for a brute force implementation. Thanks to amit for pointing that out. You could rework this to only walk the combinations, rather than the permutations, of the item set, as a first-pass optimization.

  GetMaximalCandidate(candidates[1..M])
  1. if M = 0 then return Null
  2. else then
  3.    maxel = candidates[1]
  4.    for i = 2 to M do
  5.       if weight(candidates[i]) > weight(maxel) then
  6.          maxel = candidates[i]
  7.    return maxel

Brute force implementation for 0-1 Knapsack

1 Answers