1

A person has items with below weights.

[10, 10, 12, 15, 16, 20, 45, 65, 120, 140, 150, 178, 198, 200, 210, 233, 298 , 306, 307, 310 , 375, 400, 420 , 411 , 501, 550, 662, 690 ,720, 731, 780, 790]

And the maximum weight he can carry home is 3 kg (3000 grams). He wants to cary as much as maximum.

Note i tried with backtracking algorithm but it's giving me subsets which are equal to the sum which i am looking but in a case where i can't find equal match sum then it's failed. I want to find the subset which is close to the sum.

Venkata Krishna
  • 4,287
  • 6
  • 30
  • 53
  • Why not record the current best result as you traverse and update that if the difference between the current value and the target is smaller than the previous best result? – Jon Cage Feb 11 '15 at 12:20

2 Answers2

1

This is the subset sum problem that is solveable in Dynamic Programming - which is basically an efficient implementation of your backtracking one, by following the following recursion formulas:

D(0,n) = True
D(x,0) = False  | x > 0
D(x,n) = D(x-arr[i], n-1)           OR      D(x,n-1)
               ^                                ^
       item i is in subset         item i is not in subset

By using bottom-up Dynamic Programming (creating a matrix and filling it from lower to higher) or top-down Dynamic Programming (memorizing every result and checking if it's already calculated before recursing), this is solveable in O(n*W), where n is the number of elements and W is the size of the subset (3000 in your case).

If you run bottom-up DP, the largest value of x such that D(x,n) = True, is the maximum weight one can carry. For finding the actual items, one should follow the table back, examine which items was added at each decision point, and yield the items that were added. Returning the actual set is explained with more details in the thread: How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag's value]? (This thread is dealing with knapsack problem, which is a variant of your problem, with weight=cost for each item)

Community
  • 1
  • 1
amit
  • 175,853
  • 27
  • 231
  • 333
  • Interesting side point to you answer: Do you have any reference where recursion in conjunction with memoization is called "top-down Dynamic Programming"? I have been wordering for years whether this is actually considered Dynamic programming, or if "Dynamic programming" means that no recursive calls are performed at all. – Codor Feb 11 '15 at 12:34
  • 1
    @Codor Though it's not an authority, the [wikipedia page](http://en.wikipedia.org/wiki/Dynamic_programming#Dynamic_programming_in_computer_programming) uses this terminology: – amit Feb 11 '15 at 12:40
  • `Top-down approach: This is the direct fall-out of the recursive formulation of any problem. If the solution to any problem can be formulated recursively using the solution to its subproblems, and if its subproblems are overlapping, then one can easily memoize or store the solutions to the subproblems in a table. Whenever we attempt to solve a new subproblem, we first check the table to see if it is already solved. If a solution has been recorded, we can use it directly, otherwise we solve the subproblem and add its solution to the table.` – amit Feb 11 '15 at 12:40
  • Thanks for the clarification, I wasn't aware of that! However it has the notorious `[citation needed]` tag... – Codor Feb 11 '15 at 12:41
0

Using Backtracking, we can frame the solution like this,
We will try to return the maximum weight of the subset which is nearest but also lower to the given weight using this Pseudo Code:

func(weight_till_now,curr_pos)
    if(weight_till_now > max_possible) return 0
    if(curr_pos >= N) return 0

    // Taking this weight in current subset
    weight =  max(weight_till_now,func(weight_till_now+wt[curr_pos],curr_pos+1))

    // Not taking in current subset
    weight =  max(weight_till_now,func(weight_till_now,curr_pos+1))

    return weight

Calling this function with initial parameters as 0,0 will give you the answer as this will make each and every subset and also try to get the maximum weight of all the possible subset weight and if it becomes greater than maximum possible weight then this will return 0.

Ishabh Gupta
  • 1
  • 2