1- Design a brute-force algorithm for solving the problem below (provide pseudocode): You have a large container with storage size: W lb. You have many Items (n) where each item weight is: wi. the algorithm you design should find the subset of items with the largest weight not exceeding W (Container storage capacity). 2- Submit a simple program in any language you prefer that implement your algorithm with an example test run.

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 !!!

answer:

sure does

explanation: