Answer: Provided in the explanation section
Explanation:
1. Algorithm:
Input: Container storage capacity-W, Weights of n items w[n]. w[i] represents the weight of the nth item.
Output: a subset of items with the largest weight not exceeding W.
Algorithm: To find the subset of items with the largest weight not exceeding W, we can use a recursive algorithm. We define Solve(W, i) as a solution to the problem with weight W and i items, then our recurrence can be written as:
Solve(W,i) = max(Solve(W,i-1) , w[i] + Solve(W-w[i],i-1)). We get this relation because for every item (ith) item we have two options, either we include it in our container or we do not include it.
When we do not include ith items in the container, then we have to solve the problem for remaining items with the same weight so we get Solve(W,i-1).
When we include ith items in the container, then we have to solve the problem for remaining items with the reduced weight so we get w[i] + Solve(W-w[i],i-1). Here we have added w[i] because we have included ith item in our container.
2. Using C++ Implementation:
#include<bits/stdc++.h>
using namespace std;
// this funtion finds the subset of items with the largest weight not exceeding W (Container storage capacity) and returns maximum possible weight of items
int solve(int w[],int W,int i,int n)
{
// if our weight has become zero or we have reached at the end of items then we simply return 0
if(W==0 || i==n)
return 0;
else
{
// if weight of ith item is more than W then we have only one case, we have to ingore the ith item
if(w[i]>W)
{
return solve(w,W,i+1,n);
}
else
{
//now we have two cases, we can incude ith item or we can ignore ith item
//case-1
int include_ith_item = w[i]+solve(w,W-w[i],i+1,n);
//case-2
int exclude_ith_item = solve(w,W,i+1,n);
//and we return the maximum of these two cases
if(include_ith_item>exclude_ith_item)
{
return include_ith_item;
}
else
{
return exclude_ith_item;
}
}
}
}
int main()
{
// some example data to test our funtion
int w[5] = {10,12,13,9,43};
int n=5;
int W = 50;
set <int> ::iterator it;
cout<<"The largest possible weight of subsets is: "<<solve(w,W,0,5);
}
cheers i hope this helped !!!
