The 0-1 knapsack problem is the following: a thief robbing a store finds n items

Question

The 0-1 knapsack problem is the following: a thief robbing a store finds n items. The ith item is worth v_i dollars and weighs w_i kilos with i and w_i positive integers. The thief wants to take as valuable a load as possible, but he can carry at most W kilos in his knapsack with W > 0. Which items should he take to maximize his loot? This is called the 0-1 knapsack problem because for each item, the thief must either take it or leave it behind, lie cannot take a fractional amount of an item or take an item more than once. In the fractional knapsack problem, the setup is the same, but the thief can take fractions of items, rather than having to make a binary (0-1) choice for each item. After some deep thinking the lecturer of COMP333 proposes the following modelling for the fractional knapsack problem: let S = {1, 2, ..., n} Opt(S, W) = max_1 lessthanorequalto j lessthanorequalto n, 0 lessthanorequalto p lessthanorequalto 1 p middot v_j + Opt(S{j}, W - p_j middot w_j) and Opt(Y) = 0. Notice that the 0-1 knapsack problem is a particular case where p must be either 0 or 1. Prove that the fractional knapsack problem recursive solution defined by Equation 1 has optimal sub-structure. Can you re-use your previous proof to prove that the 0-1 knapsack problem has optimal sub-structure? [If yes, you should show why, if not, provide an alternative proof.] A greedy strategy for the fractional knapsack problem is to pick up as much as we can of the item that has greatest possible value per kilo. Assume we first compute the value per kilo for each item. i.e., v_i = v_i/w_i. The greedy choice for Opt(S, W) is to take as much as we can of item i elementof S where v_i is maximal. Show that the previous greedy choice yields an optimal solution for the fractional knapsack problem. Consider the following concrete instance of the knapsack problem: the maximum capacity of the knapsack is 80 and the 4 items are as follows Compute the optimal value for the fractional version using the greedy algorithm.

Explanation / Answer

// C/C++ program to solve fractional Knapsack Problem
#include <iostream>
#include<algorithm>
using namespace std;
#define SIZE 4

struct KnapItems
{
    int val;
   int w;  
};

// This function sort the KnapItems acc to val/weight ratio
bool compare(struct KnapItems it1, struct KnapItems it2)
{
    double ratio1 = (double)it1.val / it1.w;
    double ratio2 = (double)it2.val / it2.w;
    return ratio1 > ratio2;
}

// Greedy algorithm for computing optimal value
double fractionalKS(int W, struct KnapItems arr[], int n)
{
  
    sort(arr, arr + n, compare);

    int currentWeight = 0;
   double result = 0.0; // Result (value in Knapsack)

    // For Loop for all KnapItemss
    for (int i = 0; i < n; i++)
    {
        // If adding KnapItems not overflowing then adding
        if (currentWeight + arr[i].w <= W)
        {
            currentWeight += arr[i].w;
            result += arr[i].val;
        }

        // Adding fractional part If we cannot add current KnapItems
        else
        {
            int remain = W - currentWeight;
            result += arr[i].val * ((double) remain / arr[i].w);
            break;
        }
    }

        return result;
}

// driver program to test above function
int main()
{
    int WeightOfKnapSack = 50;
    KnapItems arr[SIZE];
   arr[0].val=60;
   arr[0].w=10;

   arr[1].val=80;
   arr[1].w=8;

   arr[2].val=60;
   arr[2].w=5;

   arr[3].val=80;
   arr[3].w=15;

    cout << "Optimal value we can get is = "<< fractionalKS(WeightOfKnapSack, arr, SIZE);
    return 0;
}

OUTPUT:

Optimal value we can get is = 280

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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