Can you write a c++ or java for problem in dyanmic programing In an enumerative

Question

Can you write a c++ or java for problem in dyanmic programing

In an enumerative approach, you solve the problem of finding the set of items with the highest total value, i.e., find the “optimal set”, by identifying every subset of items. We remove from consideration those subsets that exceed the budget limit. Then, we select from the remaining (feasible) subsets to identify one having the largest total value. Many solution approaches involve some form of smart enumeration to cut down on the total amount of work (computational effort) required to find the optimal set. In a dynamic programming approach, the problem is solved using recursion. We point out that the optimal set will either contain the last item, item n, or it will not. If it doesn’t, then the optimal set is found by solving the problem with a knapsack of size B over the remaining items 1…n-1. An astute observer would recognize that if an optimal set includes item n, then the optimal set has that item plus the optimal choices among the other items 1…n-1 that would fit into the remaining space which is equivalent to a knapsack of size B-an. Let V(k, S) be a function that represents the optimal total value that could be obtain from by solving the problem by considering only items 1…k and having a sack of size S. Then the optimal value of our Knapsack Problem is V(n, B), which equals: Max(V(n-1, B), cn + V(n-1, B-an)) That is, the optimal value is the larger of the potential optimal value without item n and the potential optimal value without item n. In general the recursive equation is: V(k, S) = Max(V(k-1, s), ck + V(k-1, B-ak)). To solve the recursion we consider the following initial conditions for the function: • V(k, 0) must equal 0 for all k, because a knapsack of size 0 can’t hold any items. • V(k, S) is - when S<0 because there is no such thing as a knapsack with negative capacity. • V(1, S) must equal 0 if S < a1 because the only item to consider doesn’t fit in the knapsack and V(1, S) must be equal to c1 when S a1 because there is only one item to consider and it fits. Thus, it is possible to solve the problem by populating a two-dimensional array (matrix) for V of size (B+1)×n with these initial values and then using the recursion equation to populate additional locations until a value is found for V(n, B). You should keep track of whether the optimal solution for V(n, B) included item n or not. Then you can backtrack to find out whether item n-1 is included and so on until you know whether item 1 is included.

Explanation / Answer

Dynamic Programming:

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item, or don’t pick it (0-1 property).

A simple solution is to consider all subsets of items and calculate the total weight and value of all subsets. Consider the only subsets whose total weight is smaller than W. From all such subsets, pick the maximum value subset.

1) Optimal Substructure:
To consider all subsets of items, there can be two cases for every item: (1) the item is included in the optimal subset, (2) not included in the optimal set.
Therefore, the maximum value that can be obtained from n items is max of following two values.
1) Maximum value obtained by n-1 items and W weight (excluding nth item).
2) Value of nth item plus maximum value obtained by n-1 items and W minus weight of the nth item (including nth item).

If weight of nth item is greater than W, then the nth item cannot be included and case 1 is the only possibility.

2) Overlapping Subproblems
Following is recursive implementation that simply follows the recursive structure mentioned above.

C++ CODE:

/* A Naive recursive implementation of 0-1 Knapsack problem */
#include<stdio.h>

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

// Returns the maximum value that can be put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{
   // Base Case
   if (n == 0 || W == 0)
       return 0;

   // If weight of the nth item is more than Knapsack capacity W, then
   // this item cannot be included in the optimal solution
   if (wt[n-1] > W)
       return knapSack(W, wt, val, n-1);

   // Return the maximum of two cases:
   // (1) nth item included
   // (2) not included
   else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
                    knapSack(W, wt, val, n-1)
                  );
}

// Driver program to test above function
int main()
{
    int val[] = {60, 100, 120};
    int wt[] = {10, 20, 30};
    int W = 50;
    int n = sizeof(val)/sizeof(val[0]);
    printf("%d", knapSack(W, wt, val, n));
    return 0;
}

Output:
220

// A Dynamic Programming based solution for 0-1 Knapsack problem
#include<stdio.h>

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

// Returns the maximum value that can be put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], 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(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
           else
                 K[i][w] = K[i-1][w];
       }
   }

   return K[n][W];
}

int main()
{
    int val[] = {60, 100, 120};
    int wt[] = {10, 20, 30};
    int W = 50;
    int n = sizeof(val)/sizeof(val[0]);
    printf("%d", knapSack(W, wt, val, n));
    return 0;
}

Output:

220

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.