Question

There are many variations on the Knapsack problem. In this question, consider the same set up as the 0-1 Knapsack problem except suppose there are as many copies of each item as you would like. Thus, if one of the items is small but very valuable, it is possible to put many exact duplicates of that item into the knapsack. To maximize the value of items in the knapsack, the thief may decide to put in as many of the high value, low weight items as possible into the Knapsack

Giving up on the greedy approach and not seeing how to approach this problem using divide and conquer, you decide to try dynamic programming.

1. Specify the function that represents the quantity to be optimized.
2. Give the recurrence relation that describes the optimal substructure of the problem using
3. Give the specification of the table that you would use in a bottom up programmatic solution.   Specify the dimensions of the table and what each entry in the table represents.
4. Write the pseudo code of the algorithm for filling in the table that you would use in a bottom up programmatic solution. That is convert the recurrence relation (part B.) to an iterative algorithm.
5. Write the pseudo code of the algorithm for tracing back through the table to find the set of items that gives the maximum total value.
6. Write the asymptotic complexity of filling in the table.

Answer 1

For A and B: Following function can be used

OPT(i, w) = max(OPT(i-1, w) or vi + OPT(i, w-wi))
                     ^                   ^
          removed the element      not removing the element

// dp[i][j] -> maximum weight j  that we can have after processing i elements.
// the size of the table will be O(W)after optimisation
dp[i] = 0
dp[i] = max(dp[i], dp[i-wt[j]] + val[j] 
                   where j varies from 0 
                   to n-1 such that:
                   wt[j] <= i

result = d[W]
int unboundedKnapsack(int W, int n, 
                       int val[], int wt[])
{
    // dp[i] is going to store maximum value
    // with knapsack capacity i.
    int dp[W+1];
    memset(dp, 0, sizeof dp);
 
    // Fill dp[] using above recursive formula
    for (int i=0; i<=W; i++)
      for (int j=0; j<n; j++)
         if (wt[j] <= i)
            dp[i] = max(dp[i], dp[i-wt[j]] + val[j]);
 
    return dp[W];
}

For tracing back

// stores the result of Knapsack 
    int res = dp[n][W];     
    printf("%d\n", res); 
      
    w = W; 
    for (i = n; i > 0 && res > 0; i--) { 
          
        // either the result comes from the top 
        // (dp[i-1][w]) or from (val[i-1] + dp[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 == dp[i - 1][w])  
            continue;         
        else { 
  
            // This item is included. 
            printf("%d ", wt[i - 1]); 
              
            // Since this weight is included its  
            // value is deducted 
            res = res - val[i - 1]; 
            w = w - wt[i - 1]; 
        } 
    } 

Since we are traversing the whole table only once, the complexity will be