Part I.

class ShoppingBag

Write the classes GroceriesFileReader and SubsetSum such that class ShoppingBag and main() method will successfully:

• Read the input file that contains the prices of the different items.

• Then given the condition of how much the user's budget is, determines a list of items we can buy.

  We're at a cash only store. So, no purchases via checks or credit! We're working with a specific target in the class SubsetSum and findSubset() method.

  NOTE: Your static findSubset() method should be self-contained. This means that it should not depend on any static field (i.e. class field). If your implementation relies on these, then these class fields should be initialized every single time the user call the static methods.

• Finally, captures and outputs the estimated run time of your implementation and reports it back.

Output

Use the provided example input file to create a set and check that your algorithm finds the correct result against different test cases. Then at minimum create one additional input file and check that your algorithm finds the correct result given the new set.

Test Cases

Testing all possible combinations of budget and sets is not practical. Instead let's partition the possible inputs for budgets in a few cases. Your output should cover these three test cases:

• When budget is > sum of all elements.
• When budget is == sum of all elements and a subset of elements is found with a total that has an exact match our budget amount.
• When budget is < sum of all elements and there is no exact match. So, we return a subset of elements with closest match.

Clearly distinguish the different test cases. The example below demonstrates testing the above three test cases with two different input files.

The format of the input file is:

bananas,2.50 beans,4 beef,11.50 chicken,7 fish,15 juice,4 milk,6 ramen,8

package subsetsum;
	import java.util.ArrayList;
	import java.util.Scanner;
	/**
	* An object of type ShoppingBag class creates an object of type subset sum to find a best
	* possible grocery shopping list within the given budget.
	*
	* REMINDER: Include test cases in addition to those provided.
	* Do this by creating your own input file.
	* Test your implementation against various budgets, including boundary cases.
	public class ShoppingBag
	{
	private ArrayList priceOfGroceries;
	/**
	* Parameterized constructor for an object of class ShoppingBag.
	* Reads in a file and adds the prices into a list of the prices of groceries
	* @param filePath The input file to parse.
	*/
	public ShoppingBag(String filePath)
	{
	// TODO: Define the class GroceriesFileReader
	GroceriesFileReader reader = new GroceriesFileReader();
	// TODO: Define the readFile() method which reads the CSV (Comma Seperated Value) file
	// of groceries and creates a specified ArrayList of grocery prices.
	//
	// NOTE: Catch all exceptions in the GroceriesFileReader readFile() method.
	// That means readFile() method should not throw an exception.
	priceOfGroceries = reader.readFile(filePath);
	// Check the size of the resulting ArrayList object.
	if (priceOfGroceries.size() < 1)
	{
	System.out.println("WARNING: The list of groceries is empty.");
	return;
	}
	System.out.printf("The list of groceries has %d items. ", priceOfGroceries.size());
	}
	/**
	* Accessor method returns the list of items read from input file.
	* @return the price of groceries.
	*/
	public ArrayList getPriceOfGroceries()
	{
	return priceOfGroceries;
	}
	/**
	* Reads an input file that contains the prices of the different items.
	* Then stores and outputs a list of items we can buy
	* given the condition of how much money you have in your wallet.
	* We're at a cash only store. So, no checks or credit purchases!
	* @param args Not used.
	*/
	public static void main(String[] args)
	{
	// NOTE: Make sure to use *relative* path instead of specifying the entire path.
	// Otherwise, your program will result in run time errors when the instructor
	// tests your implementation.
	final String FILEPATH = "resources/groceries.txt";
	ShoppingBag bag = new ShoppingBag(FILEPATH);
	ArrayList shoppingList = bag.getPriceOfGroceries();
	// displays the prices of items in the input file
	System.out.println("Groceries wanted:");
	System.out.println(shoppingList);
	// prompt the user for their budget
	Scanner keyboard = new Scanner(System.in);
	double budget = -1;
	do
	{
	// REMINDER: Test your implementation against various budgets, including boundary cases.
	System.out.println(" Enter your budget:");
	String input = keyboard.nextLine();
	// Specifies that a valid input is a regular expression, which
	// is at least one digit long and can have decimal positions.
	String validInputPattern = "[0-9]+[0-9]*.*[0-9]*";
	if (!input.matches(validInputPattern))
	{
	System.out.println("Invalid input " + input);
	System.out.println("Enter a numeric value for the budget.");
	continue;
	}
	budget = Double.parseDouble(input);
	} while(budget < 0);
	// for measuring run time
	long startTime, estimatedTime;
	// capture the start time
	startTime = System.nanoTime();
	// TODO: implement finding subset of groceries that is closest to meeting the user's budget.
	// NOTE: In this part, you only need to keep track of the price of each item,
	// and not the name of the item you are buying.
	ArrayList purchases = SubsetSum.findSubset(shoppingList, budget);
	// stop the timer
	estimatedTime = System.nanoTime() - startTime;
	// report algorithm time
	System.out.println(" Algorithm Elapsed Time: "
	+ TimeConverter.convertTimeToString(estimatedTime));
	System.out.println("Purchased grocery prices are:");
	System.out.println(purchases);
	System.err.flush();
	System.out.println("Done with ShoppingBag.");
	}
	}