CODEWITHSUNDEEP
calgorithmlinear-algebradynamic-programmingknapsack-problem
Voyage_Mystere
Voyage_Mystere

Reputation: 159

how to modify Knapsack - to find the maximum weighted sum

The below is a knapsack code using dynamic programming. The original code will return a maximum sum of the values. However, I want to tweak it so that the code will return a maximum sum of (value*weight). The below is what I have done, but it doesn't work well, some advice is appreciated. 

 #include<stdio.h>
int max(int a,int b)
{
        return a>b?a:b;
}
int Knapsack(int items,int weight[],int value[],int maxWeight)
{
        int dp[items+1][maxWeight+1];
        /* dp[i][w] represents maximum value that can be attained if the maximum weight is w and
           items are chosen from 1...i */
        /* dp[0][w] = 0 for all w because we have chosen 0 items */
        int iter,w;
        for(iter=0;iter<=maxWeight;iter++)
        {
                dp[0][iter]=0;
        }
        /* dp[i][0] = 0 for all w because maximum weight we can take is 0 */
        for(iter=0;iter<=items;iter++)
        {
                dp[iter][0]=0;
        }
        for(iter=1;iter<=items;iter++)
        {
                for(w=0;w<=maxWeight;w=w+10)
                {
                        dp[iter][w] = dp[iter-1][w]*weight[iter-1]; /* If I do not take this item */
                        if(w-weight[iter] >=0)
                        {
                                /* suppose if I take this item */
                                dp[iter][w] = max( (dp[iter][w]*weight[iter]) , (dp[iter-1][w-weight[iter]]*weight[iter-1])+(value[iter]*weight[iter]));
                        }
                }

        }
        return dp[items][maxWeight];
}
int main()
{
        int items=12;
        int weight[/*items+1*/13]={60, 20, 20, 20, 10, 20, 10, 10, 10, 20, 20, 10};
        int value[/*items+1*/13]={48, 77, 46, 82, 85, 43, 49, 73, 65, 48, 47, 51};
        int iter;

        int maxWeight=120;
        printf("Max value attained can be %d\n",Knapsack(items,weight,value,maxWeight));
}

The code is expected to give an output of Max value attained can be 7820 (the maximum total sum of value*weight calculated by hand). However, the output is Max value attained can be 0. Why?

Upvotes: 1

Views: 1859

Answers (1)

Abhishek Bansal
Abhishek Bansal

Reputation: 12715

I think the problem can be solved simply by making the following change:

In the original knapsack problem, change all values to value*weight and proceed normally to maximize the total value.

http://en.wikipedia.org/wiki/Knapsack_problem

It should come to the same if you change:

dp[iter][w] = dp[iter-1][w]*weight[iter-1]; /* If I do not take this item */
if(w-weight[iter] >=0)
{
  /* suppose if I take this item */
  dp[iter][w] = max( (dp[iter][w]*weight[iter]) , (dp[iter-1][w-weight[iter]]*weight[iter-1])+(value[iter]*weight[iter]));
}

to

dp[iter][w] = dp[iter-1][w]; /* If I do not take this item */
if(w-weight[iter] >=0)
{
  /* suppose if I take this item */
  dp[iter][w] = max( dp[iter][w] , (dp[iter-1][w-weight[iter]]+(value[iter]*weight[iter]));
}

Upvotes: 2

Related Questions