Question

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

Answer 1

ANSWER :-

Language : C++

//0-1 Knapsack problem using Greedy approach
#include<iostream>        
using namespace std;
// function that returns maximum of two integers
int maximum(int a, int b)
{
        return (a > b) ? a : b;
}
         
// Returns the maximum value that can be put in a knapsack of capacity W
int GreedyknapSack(int mw, int weight[], int val[], int n)
{
        // Base Case
        if (n == 0 || mw == 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 (weight[n - 1] > mw)
        return GreedyknapSack(mw, weight, val, n - 1);
        
        // Return the maximum of two cases: (1) nth item included (2) not included
        else
        return maximum(val[n - 1] + GreedyknapSack(mw - weight[n - 1], weight, val, n - 1),
        GreedyknapSack(mw, weight, val, n - 1));
}
 

int main()
{
        cout << "Enter number of items in Knapsack:";
        int n, mw;
        cin >> n;
        int val[n], weight[n];
        for (int i = 0; i < n; i++)
        {
                cout << "Enter profit & weight for "<< i << " item :";
                cin >> val[i];
                cin >> weight[i];
        }
 
        cout <<"Enter max weight: ";
        cin >> mw;
        cout <<"Knapsack value is: "<< GreedyknapSack(mw, weight, val, n);
        return 0;
}

Output :-