CODEWITHSUNDEEP
algorithm
Venkata Krishna
Venkata Krishna

Reputation: 4305

Find the max weight subset which to carry

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.

Upvotes: 1

Views: 878

Answers (2)

Ishabh Gupta
Ishabh Gupta

Reputation: 1

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.

Upvotes: 0

amit
amit

Reputation: 178461

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)

Upvotes: 1

Related Questions