Question

In: Advanced Math

The Knapsack problem is an optimization problem that asks to fill a knapsack with maximum possible...

The Knapsack problem is an optimization problem that asks to fill a knapsack with maximum possible value. Using greedy paradigm, we can solve this problem easily. Your task is the following:

(a) Write the pseudo-code of a greedy solution for knapsack problem.
(b) Give is the time complexity of your solution in part (a).
(c) Implement part (a) in C programming language.

Solutions

Expert Solution

Given weights and values of n items, we need to put these items in a knapsack of capacity W to get the maximum total value in the knapsack.

In the 0-1 Knapsack problem, we are not allowed to break items. We either take the whole item or don’t take it.

Input:
  Items as (value, weight) pairs
  arr[] = {{60, 10}, {100, 20}, {120, 30}}
  Knapsack Capacity, W = 50;
Output:
  Maximum possible value = 220
  by taking items of weight 20 and 30 kg 

Recommended: Please solve it on “PRACTICE ” first, before moving on to the solution.


In Fractional Knapsack, we can break items for maximizing the total value of knapsack. This problem in which we can break an item is also called the fractional knapsack problem.

Input : 
   Same as above
Output :
   Maximum possible value = 240
   By taking full items of 10 kg, 20 kg and 
   2/3rd of last item of 30 kg

A brute-force solution would be to try all possible subset with all different fraction but that will be too much time taking.

An efficient solution is to use Greedy approach. The basic idea of the greedy approach is to calculate the ratio value/weight for each item and sort the item on basis of this ratio. Then take the item with the highest ratio and add them until we can’t add the next item as a whole and at the end add the next item as much as we can. Which will always be the optimal solution to this problem.

A simple code with our own comparison function can be written as follows, please see sort function more closely, the third argument to sort function is our comparison function which sorts the item according to value/weight ratio in non-decreasing order.
After sorting we need to loop over these items and add them in our knapsack satisfying above-mentioned criteria.

  • C++
  • Java
  • Python3

filter_none

edit

play_arrow

brightness_4

// C/C++ program to solve fractional Knapsack Problem

#include <bits/stdc++.h>

  

using namespace std;

  

// Structure for an item which stores weight and corresponding

// value of Item

struct Item

{

    int value, weight;

  

    // Constructor

    Item(int value, int weight) : value(value), weight(weight)

    {}

};

  

// Comparison function to sort Item according to val/weight ratio

bool cmp(struct Item a, struct Item b)

{

    double r1 = (double)a.value / a.weight;

    double r2 = (double)b.value / b.weight;

    return r1 > r2;

}

  

// Main greedy function to solve problem

double fractionalKnapsack(int W, struct Item arr[], int n)

{

    //    sorting Item on basis of ratio

    sort(arr, arr + n, cmp);

  

    //    Uncomment to see new order of Items with their ratio

    /*

    for (int i = 0; i < n; i++)

    {

        cout << arr[i].value << " " << arr[i].weight << " : "

             << ((double)arr[i].value / arr[i].weight) << endl;

    }

    */

  

    int curWeight = 0; // Current weight in knapsack

    double finalvalue = 0.0; // Result (value in Knapsack)

  

    // Looping through all Items

    for (int i = 0; i < n; i++)

    {

        // If adding Item won't overflow, add it completely

        if (curWeight + arr[i].weight <= W)

        {

            curWeight += arr[i].weight;

            finalvalue += arr[i].value;

        }

  

        // If we can't add current Item, add fractional part of it

        else

        {

            int remain = W - curWeight;

            finalvalue += arr[i].value * ((double) remain / arr[i].weight);

            break;

        }

    }

  

    // Returning final value

    return finalvalue;

}

  

// driver program to test above function

int main()

{

    int W = 50;   //    Weight of knapsack

    Item arr[] = {{60, 10}, {100, 20}, {120, 30}};

  

    int n = sizeof(arr) / sizeof(arr[0]);

  

    cout << "Maximum value we can obtain = "

         << fractionalKnapsack(W, arr, n);

    return 0;

}


Output :

Maximum value in Knapsack = 240

As main time taking step is sorting, the whole problem can be solved in O(n log n) only.


Related Solutions

The Knapsack problem is an optimization problem that asks to fill a knapsack with maximum possible...
The Knapsack problem is an optimization problem that asks to fill a knapsack with maximum possible value. Using greedy paradigm, we can solve this problem easily. Your task is the following: (a) Write the pseudo-code of a greedy solution for knapsack problem. (b) Give is the time complexity of your solution in part (a). (c) Implement part (a) in C programming language.
KNAPSACK Optimization Problem using Greedy Method Problem 1: Item Weight Value 1 14 20 2 6...
KNAPSACK Optimization Problem using Greedy Method Problem 1: Item Weight Value 1 14 20 2 6 16 3 10 8 4 5 10 5 4 12 Allowed weight = 24 Kg Problem 2: Item Weight Value 1 6 30 2 8 40 3 15 45 4 22 88 5 25 80 Allowed weight = 60 Kg Problem 3: Item Weight Value 1 6 30 2 8 40 3 15 45 4 22 88 5 25 80 Allowed weight = 60...
In a typical optimization problem (max/min problem), we want to find a relative maximum or relative...
In a typical optimization problem (max/min problem), we want to find a relative maximum or relative minimum of a function. Our process is to • find the derivative of the function, • set that derivative equal to zero, • and solve for x. Use complete sentences to explain why this process makes sense.
Knapsack algorithm problem: Consider the following variation of the Knapsack problem. There are n types of...
Knapsack algorithm problem: Consider the following variation of the Knapsack problem. There are n types of items, let call them 1,2,3,4,...,n. There are exactly c_i copies of item i, and each such copy has value v_i and weight w_i. As before, the knapsack capacity is W, and the other constraint is that you can only take at most c_i copies of item i ( since no more are available). Show how to compute the optimal value that can be achieved...
Optimization Problem
We want to construct a box whose base length is three times the base width. The material used to build the top and bottom cost $10/ft2 and the material to build the sides cost $6/ft2 . If the box must have volume 50 ft3 , what is the minimum cost of the box?
Solve the following optimization problem (Be sure to include the statement of the optimization problem and...
Solve the following optimization problem (Be sure to include the statement of the optimization problem and a graph of the feasible in your solution): Jamie has joined a building contest. A dog shape requires 3 small blocks and one large block to build. A robot shape requires 5 small bricks and 5 large bricks to build. Jamie has a supply of 240 small bricks and 100 large bricks. If a dog is worth 2 points and a robot is worth...
Optimization problem for calculus 3. Possible use of Lagrange Multiple? Question: What are the largest and...
Optimization problem for calculus 3. Possible use of Lagrange Multiple? Question: What are the largest and smallest outputs of the function x 2+2y2 on the ellipse x2+y2+xy=3
Urgent! How do you do solve a knapsack problem recursively in JAVA. for an arbitrary knapsack...
Urgent! How do you do solve a knapsack problem recursively in JAVA. for an arbitrary knapsack capacity and series of weights. Assume the weights are sorted in an array. **The arguments to the knapsack function are target weight and the array index where the remaining items start. For example if you want your knapsack to weigh exactly 20 pounds and you have five items with weights of 11,8,7,6 and 5 pounds. In this case only combination that works is 8,...
how to write a genetic algorithm for a knapsack problem .
how to write a genetic algorithm for a knapsack problem .
Explain the concept of optimization. Explain the general procedure used to do an optimization problem. Use...
Explain the concept of optimization. Explain the general procedure used to do an optimization problem. Use an example and include steps
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT