Question

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 Java that implements your algorithm with an example test run.

Answer 1

Answer:

Pseudocode is as follows:

// below is a function that takes two parameters:1. An array of items 2. An integer for weight W

// it returns an array of selected items which satisfy the given condition of sum <= max sum.

function findSubset( array items[], integer W)

{

initialize:

maxSum = 0;

ansArray = [];

// take each "item" from array to create all possible combinations of arrays by comparing with "W" and // "maxSum"

start the loop:

// include item in the ansArray[]

ansArray.push(item);

// remove the item from the items[]

items.pop(item);

ansArray.push(item1);

start the while loop(sum(ansArray[]) <= W):

// exclude the element already included and start including till

if (sum(ansArray[]) > maxSum)

// if true then include item in ansArray[]

ansArray.push(item);

// update the maxSum

maxSum = sum(ansArray[items]);

else

// move to next element

continue;

end the loop;

// again make the item[] same by pushing the popped element

items.push(item);

end the loop;

return the ansArray[]

}

Explanation:

You can find example to implement the algorithm.