Question

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 in a knapsack of capacity W. To solve the problem show how to formulate it recursively, the recurrence, discuss the subproblem etc.

Answer 1

It is request to please don't leave without thumbs up I really need it so that I can provide quality answer to you hoping for good thank you!

I have answer this question according to the question in my language and provided the code below and adding comment so that you can understand well , hope you like and please don't dislike

If You have Any Query Regarding this please ask in comment section I will be there to solve all your query in comment section immediately hope you will like it

In 0-1 Knapsack problem, you are given a Knapsack or a bag and several items with their weight and profit. The bag has a maximum capacity of weight it can hold. Now your task is to maximise the profit by choosing several items. It is called 0-1 because of the decision values, either an item will be taken or it will be discarded.
The right approach to solve it is using DP (dynamic programming) , but you can also solve using recursive as in question it ask for recursive solution. Let the capacity of Knapsack be W, and there be N items, Wt[] be the array of weights :Wi be the weight of ith item; Val[] be the of cost of copies : val_i be the optimal gained by ith item.

//PLAESE DO THUMBS UP / UPVOTE FOR MY EFFORTS AND DON'T LEAVE WITHOUT UPVOTE THANKYOU
#include <bits/stdc++.h>//=+
using namespace std;

//this function will return the maximum capacity it can hold
// is it can  put in a knapSack_bag of capacity W
int knapSack_recursive(int W, int wt_copies[], int val_copies[], int n)
{

        // Base Case when item and size of knapsack is zero
        if (n == 0 || W == 0)
                return 0;
     //condtion while putting item in knapsack bag
        // If weight of the nth item is more
        // than knapSack_bag capacity W, then
        // this item cannot be included
        // in the optimal solution
        if (wt_copies[n-1] > W)
                return knapSack_recursive(W, wt_copies, val_copies, n - 1);

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

// Driver code
int main()
{
    int n ,W;
    cout<<"enter the no of items \n";
    cin>>n;

        int val_copies[1000], wt_copies[1000];
        cout<<"enter the copies\n ";
        for(int i=0;i<n;i++)
        cin>>val_copies[i];
        cout<<"enter the weight of diffrent copies\n";
    for(int i=0;i<n;i++)
        cin>>wt_copies[i];
    cout<<"enter the size of knapsack bag\n";
    cin>>W;
        cout <<"Optimal cost will be  : " << knapSack_recursive(W, wt_copies, val_copies, n);
        return 0;
}

Output :