Question

In: Computer Science

Part1: Write a program in C/C++ to solve the 0/1 knapsack problem using (i) Dynamic Programming...

Part1: Write a program in C/C++ to solve the 0/1 knapsack problem using (i) Dynamic Programming based algorithm and (ii) Branch and Bound Search based algorithm Go through the related text and implement each of these algorithms using the efficient data structure. Show the results of different steps of these algorithms for an instance of the 0/1 Knapsack problem with number of items, n=4. The capacity of the knapsack, weights and profits of the items may be generated randomly with the condition that the capacity of the knapsack is such that all items can not be accommodated in the knapsack. But, at the same time, at least one item can be accommodated in the knapsack. Part2: Analyze the complexity of these algorithms (Run each of the two algorithms for a set of ten randomly generated 0/1 knapsack instances (with n=4) and compute the time taken by the selected implementation in each run. Compute average time taken by each of these two algorithms

Solutions

Expert Solution

Part 1)

i) DP approach-


int knapsack(int val[], int wt[], int W, int n){

int dp[n+1][W+1];

if(n==0 || W==0)
return 0;

        for(int i=0;i<=n;i++) dp[i][0]=0;
        for(int i=0;i<=W;i++) dp[0][i]=0;

        for(int i=1;i<=n;i++){
            for(int j=1;j<=W;j++){

                    int maxWithoutItem=dp[i-1][j];

                    int maxWithItem=0;
                        int wtofitem=wt[i-1];
                    if(j>=wtofitem){
                        maxWithItem=val[i-1];
                        int remainingcapacity= j-wtofitem;
                        maxWithItem+=dp[i-1][remainingcapacity];
                    }                
            
            dp[i][j]=max(maxWithoutItem,maxWithItem);
        }
        }

    return dp[n][W];
}


int main() {
    //cout<<"Hello World!";

int n=4;
int W=10;

    int val[]={10,40,30,50};
    int wt[] ={5,4,6,3};

    cout<<"Maximum profit earned is: "<<knapsack(val,wt,W,n);


    return 0;
}

Time complexity- O(n*W)

Space Complexity- O(n*W)

ii) Branch and Bound approach-

Complete Algorithm:

  1. Sort all items in decreasing order of ratio of value per unit weight so that an upper bound can be computed using Greedy Approach.
  2. Initialize maximum profit, maxProfit = 0
  3. Create an empty queue, Q.
  4. Create a dummy node of decision tree and enqueue it to Q. Profit and weight of dummy node are 0.
  5. Do following while Q is not empty.
    • Extract an item from Q. Let the extracted item be u.
    • Compute profit of next level node. If the profit is more than maxProfit, then update maxProfit.
    • Compute bound of next level node. If bound is more than maxProfit, then add next level node to Q.
    • Consider the case when next level node is not considered as part of solution and add a node to queue with level as next, but weight and profit without considering next level nodes
#include <bits/stdc++.h> 
using namespace std; 

// Structure for Item which store weight and corresponding 
// value of Item 
struct Item 
{ 
        float weight; 
        int value; 
}; 

// Node structure to store information of decision 
// tree 
struct Node 
{ 
        // level --> Level of node in decision tree (or index 
        //                       in arr[] 
        // profit --> Profit of nodes on path from root to this 
        //               node (including this node) 
        // bound ---> Upper bound of maximum profit in subtree 
        //               of this node/ 
        int level, profit, bound; 
        float weight; 
}; 

// Comparison function to sort Item according to 
// val/weight ratio 
bool cmp(Item a, Item b) 
{ 
        double r1 = (double)a.value / a.weight; 
        double r2 = (double)b.value / b.weight; 
        return r1 > r2; 
} 

// Returns bound of profit in subtree rooted with u. 
// This function mainly uses Greedy solution to find 
// an upper bound on maximum profit. 
int bound(Node u, int n, int W, Item arr[]) 
{ 
        // if weight overcomes the knapsack capacity, return 
        // 0 as expected bound 
        if (u.weight >= W) 
                return 0; 

        // initialize bound on profit by current profit 
        int profit_bound = u.profit; 

        // start including items from index 1 more to current 
        // item index 
        int j = u.level + 1; 
        int totweight = u.weight; 

        // checking index condition and knapsack capacity 
        // condition 
        while ((j < n) && (totweight + arr[j].weight <= W)) 
        { 
                totweight += arr[j].weight; 
                profit_bound += arr[j].value; 
                j++; 
        } 

        // If k is not n, include last item partially for 
        // upper bound on profit 
        if (j < n) 
                profit_bound += (W - totweight) * arr[j].value / 
                                                                                arr[j].weight; 

        return profit_bound; 
} 

// Returns maximum profit we can get with capacity W 
int knapsack(int W, Item arr[], int n) 
{ 
        // sorting Item on basis of value per unit 
        // weight. 
        sort(arr, arr + n, cmp); 

        // make a queue for traversing the node 
        queue<Node> Q; 
        Node u, v; 

        // dummy node at starting 
        u.level = -1; 
        u.profit = u.weight = 0; 
        Q.push(u); 

        // One by one extract an item from decision tree 
        // compute profit of all children of extracted item 
        // and keep saving maxProfit 
        int maxProfit = 0; 
        while (!Q.empty()) 
        { 
                // Dequeue a node 
                u = Q.front(); 
                Q.pop(); 

                // If it is starting node, assign level 0 
                if (u.level == -1) 
                        v.level = 0; 

                // If there is nothing on next level 
                if (u.level == n-1) 
                        continue; 

                // Else if not last node, then increment level, 
                // and compute profit of children nodes. 
                v.level = u.level + 1; 

                // Taking current level's item add current 
                // level's weight and value to node u's 
                // weight and value 
                v.weight = u.weight + arr[v.level].weight; 
                v.profit = u.profit + arr[v.level].value; 

                // If cumulated weight is less than W and 
                // profit is greater than previous profit, 
                // update maxprofit 
                if (v.weight <= W && v.profit > maxProfit) 
                        maxProfit = v.profit; 

                // Get the upper bound on profit to decide 
                // whether to add v to Q or not. 
                v.bound = bound(v, n, W, arr); 

                // If bound value is greater than profit, 
                // then only push into queue for further 
                // consideration 
                if (v.bound > maxProfit) 
                        Q.push(v); 

                // Do the same thing, but Without taking 
                // the item in knapsack 
                v.weight = u.weight; 
                v.profit = u.profit; 
                v.bound = bound(v, n, W, arr); 
                if (v.bound > maxProfit) 
                        Q.push(v); 
        } 

        return maxProfit; 
} 


int main() 
{ 
        int W = 10; // Weight of knapsack 
        Item arr[] = {{2, 40}, {3.14, 50}, {1.98, 100}, 
                                {5, 95}}; 
        int n = sizeof(arr) / sizeof(arr[0]);  // n=4

        cout << "Maximum possible profit = "
                << knapsack(W, arr, n); 

        return 0; 
} 

Time Complexity- Exponential because we are exploring all permutations in worst case.

Space Complexity -O(n)

Part 2)

Complexities have already been discussed.

Average computing time for DP approach is- 0.00145 s

Average computing time for Branch and Bound approach- 0.00187s


Related Solutions

In C++ or Java Write the Greedy programming Algorithm for the 0-1 Knapsack problem.                    (a)...
In C++ or Java Write the Greedy programming Algorithm for the 0-1 Knapsack problem.                    (a) No fraction allowed Max Weight W= 9 item 1: profit $20, weight 2, prof/weight=$10 item 2: profit $30, weight 5, prof/weight=$6 item 3: profit $35, weight 7, prof/weight=$5 item 4: profit $12, weight 3, prof/weight=$4 item 5: profit $3, weight 1, prof/weight=$3
Provide the dynamic-programming recurrence for a function that is used to solve 0-1 Knapsack. Clearly define...
Provide the dynamic-programming recurrence for a function that is used to solve 0-1 Knapsack. Clearly define what the function is computing.
Recall the dynamic programming algorithm we saw in class for solving the 0/1 knapsack problem for...
Recall the dynamic programming algorithm we saw in class for solving the 0/1 knapsack problem for n objects with a knapsack capacity of K. In particular, we characterized our recurrence OPT(j, W) to be following quantity: OPT(j, W) := The maximum profit that can be obtained when selecting from objects 1, 2, . . . , j with a knapsack capacity of W , where (after filling in our dynamic programming table), we return the value stored at OPT(n, K)...
C Program: How do I write a Greedy function for 0-1 knapsack, to find total value...
C Program: How do I write a Greedy function for 0-1 knapsack, to find total value only( replace struct Knapsack) # include #include #include struct Knapsack {    int value;    int weight; };    // 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    struct Knapsack knapSackExhaustive(int W, int wt[], int...
PRACTICAL 10 C PROGRAMMING. Question 1 - Reading into a dynamic array. Write a program called...
PRACTICAL 10 C PROGRAMMING. Question 1 - Reading into a dynamic array. Write a program called temperatures01 that reads a (non-empty) sequence maximum daily temperatures. Your program should first ask for the number of temperatures to read and dynamically allocate an array just big enough to hold the number of temperatures you read. You should then read in the elements of the array using a loop. You then should print out the elements of the array in reverse order (from...
Implement the dynamic algorithm of 0-1 knapsack problem in Java. The following table shows 10 items,...
Implement the dynamic algorithm of 0-1 knapsack problem in Java. The following table shows 10 items, their values and weights. The maximum weight capacity of the knapsack is 113. What could be the maximum value of the knapsack and the most valuable set of items that fit in the knapsack? Item Weight Value 1 32 727 2 40 763 3 44 60 4 20 606 5 1 45 6 29 370 7 3 414 8 13 880 9 6 133...
What are the different algorithms we may use to solve the 0/1 Knapsack problem? Compare and...
What are the different algorithms we may use to solve the 0/1 Knapsack problem? Compare and contrast the different methods.
5. Design a dynamic programming algorithm to solve the following problem. Input: An array A[1, ....
5. Design a dynamic programming algorithm to solve the following problem. Input: An array A[1, . . . , n] of positive integers, an integer K. Decide: Are there integers in A such that their sum is K. (Return T RUE or F ALSE) Example: The answer is TRUE for the array A = [1, 2, 3] and 5, since 2 + 3 = 5. The answer is FALSE for A = [2, 3, 4] and 8. Note that you...
3. Solve using probabilistic dynamic programming: I would like to sell my computer to the highest...
3. Solve using probabilistic dynamic programming: I would like to sell my computer to the highest bidder. I have studied the market, and concluded that I am likely to receive three types of offers: an offer of $200 with probability 2/7, and offer of $300 with probability 4/7, and an offer of $400 with probability 1/7. I will advertise my computer for up to three consecutive days. At the end of each of the three days, I will decide whether...
write pseudocode not c program If- else programming exercises 1.    Write a C program to find...
write pseudocode not c program If- else programming exercises 1.    Write a C program to find maximum between two numbers. 2.    Write a C program to find maximum between three numbers. 3.    Write a C program to check whether a number is negative, positive or zero. 4.    Write a C program to check whether a number is divisible by 5 and 11 or not. 5.    Write a C program to check whether a number is even or odd. 6.    Write...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT