Answer to Question #241172 in C for xyz

Question

Unimart is offering a dhamaka offer. Terms and conditions to gain the offer as follows: Unimart will provide a shopping bag which you can carry W weight at maximum load. (If you try to load more than W weight then it will fall on the ground and you will lose the offer forever) Unimart has N < 10 products with weight w1, w2, w3...etc. You can get only 1 product for each item. Input: W N maximum weight and number of products. Find the set of products and their sum so that you can use the maximum weight of your bag capacity. N integers represent weight product P1, P2....Pn. Output: Print selected products set and the sum of these products. Sample Input: 10 4 8 9 2 4 20 4 10 7 4 5 90 8 23 10 1 7 2 3 4 5 Sample Output: 8 2 Sum: 10 10 5 4 Sum: 19 23 10 1 2 3 4 5 7 Sum: 55 Output product set sequence doesn't matter but you have to find the optimal sum of weight so that maximizes the profit.

Answer 1

Method 1:Brute-Force algorithm.

Approach: Consider all subsets of items and calculate the total weight and value of all subsets for a simple solution. Consider the subsets with total weights that are equal to or close to W. Choose the subset with the highest value from all of them.

Method 2: Dynamic programming

Approach:

Using a 2-d array we can build using a bottom-up approach. Let say K is a 2-d array of size (n+1, W+1), we fill K[][] using following below program.

#include <stdio.h>

// function that returns maximum of two integers
int max(int a, int b) { return (a > b) ? a : b; }

// Prints the items which are put in a knapsack of capacity W
void printknapSack(int W, int wt[], int n)
{
    int i, w;
    int K[n + 1][W + 1];

    // Build table K[][] in bottom up manner
    for (i = 0; i <= n; i++) {
        for (w = 0; w <= W; w++) {
            if (i == 0 || w == 0)
                K[i][w] = 0;
            else if (wt[i - 1] <= w)
                K[i][w] = max(wt[i - 1] +
                    K[i - 1][w - wt[i - 1]], K[i - 1][w]);
            else
                K[i][w] = K[i - 1][w];
        }
    }

    // stores the result of Knapsack
    int res = K[n][W];


    w = W;
    for (i = n; i > 0 && res > 0; i--) {

        // either the result comes from the top
        // (K[i-1][w]) or from (wt[i-1] + K[i-1]
        // [w-wt[i-1]]) as in Knapsack table. If
        // it comes from the latter one/ it means
        // the item is included.
        if (res == K[i - 1][w])
            continue;
        else {

            // This item is included.
            printf("%d ", wt[i - 1]);

            // Since this weight is included its
            // weight is deducted
            res = res - wt[i - 1];
            w = w - wt[i - 1];
        }
    }
    printf("Sum:%d\n", K[n][W]);
}

// Driver code
int main()
{
    int wt[] = { 23, 10, 1, 7, 2, 3, 4, 5 };
    int W = 90;
    int n = 8;
    printknapSack(W, wt,  n);

    return 0;
}