Knapsack

java.lang.Object
- Knapsack

```
public class Knapsack
extends java.lang.Object
```
This program is a coded version of the Knapsack problem, which asks how to find the optimal value for a number of weights in a knapsack without exceeding a weight limit. In this version of the problem, the value of an object is equal to its weight, so the goal is to obtain the maximum weight possible from the objects without exceeding the limit. The program takes the name of a file with the tests to be run in the command-line arguments then prints out the result of the tests (the items to put in the bag because they have the highest weight value without going over the limit) to the output file knapsack.txt.

Author:

AnneMarie Caballero (annemariecabs)

Field Summary

Fields
Modifier and Type	Field	Description
`private static java.lang.String`	`COMMA`	A comma.
`private static java.lang.String`	`EMPTY_STRING`	Empty string.
`private static int`	`ERROR_CODE`	The number used as a parameter for System.exit() if the program has to quit early due to difficulties during runtime.
`private static java.lang.String`	`EXIT_PHRASE`	A typed phrase used if the user wants to exit the program rather than inputting information.
`private static java.lang.String`	`FILE_DOES_NOT_EXIST_MESSAGE`	The message shown when a test file does not exist.
`private static java.lang.String`	`IOEXCEPTION_MESSAGE`	The message shown if the program encounters an IOException when reading String arrays from files
`private static java.util.Scanner`	`keyboard`	A Scanner object which will be used to read user input.
`private static java.lang.String`	`NEW_LINE`	A new-line character.
`private static java.lang.String`	`NO_INTEGERS_MESSAGE`	The message shown when the file does not contain integers in the proper format.
`private static java.lang.String`	`NO_POSSIBILITIES_MESSAGE`	The message shown when there is no possible combination that is under the limit.
`private static java.io.PrintWriter`	`output`	A PrintWriter field to write to the output file, which will be used in the main and other methods.
`private static java.lang.String`	`OUTPUT_NAME`	A field representing the String literal that is the name of the output file.
`private static java.lang.String`	`PRINTWRITER_ERROR_MESSAGE`	The error message used if a PrintWriter throws a FileNotFoundException
`private static java.lang.String`	`SPACE`	A space.
`private static java.lang.String`	`TAB`	A tab.
`private static java.lang.String`	`TESTS_FILE_NOT_FOUND_MESSAGE`	The message used if the file with the names of test files is not found.
`private static java.lang.String`	`UNIT`	Printed after every watermelon weight that gets added to the knapsack in knapsack.txt.
`private static java.util.List<java.lang.Integer>`	`watermelons`	The list where the chosen objects for a problem are stored.

Constructor Summary

Constructors
Constructor Description

Knapsack()

Constructors
Constructor	Description
`Knapsack()`

Method Summary

All Methods Static Methods Concrete Methods
Modifier and Type	Method	Description
`static int`	`knapsackSum(int[] w, int n, int limit)`	A method that finds the optimal sum of weights that can still fit in the knapsack recursively.
`static int`	`knapsackSum(int[] w, int n, int limit, java.util.List<java.lang.Integer> list)`	A method that finds the solution to the knapsack problem and remembers the items used to achieve that maximum weight without going over the limit.
`static void`	`main(java.lang.String[] args)`
`private static java.util.ArrayList<java.lang.String>`	`readFileWithStringArray(java.lang.String inputName)`	An internal method that reads a file and returns its lines as a String array.
`private static java.lang.Integer[]`	`readItemsFromFile(java.lang.String inputName)`	An internal method that reads the integers within a file.
`private static void`	`writeTestToFile(java.lang.String fileName, int limit, int[] w)`	Writes a test class for knapsack to the file "knapsack.txt." It prints the file name, limit, and weights onto the file then prints the best combination of watermelons (the one that will attain the most weight without going over the limit by calling the second knapsack method.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - OUTPUT_NAME
```
private static final java.lang.String OUTPUT_NAME
```
    A field representing the String literal that is the name of the output file.
    
    See Also:
    
    Constant Field Values
  - EXIT_PHRASE
```
private static final java.lang.String EXIT_PHRASE
```
    A typed phrase used if the user wants to exit the program rather than inputting information.
    
    See Also:
    
    Constant Field Values
  - ERROR_CODE
```
private static final int ERROR_CODE
```
    The number used as a parameter for System.exit() if the program has to quit early due to difficulties during runtime.
    
    See Also:
    
    Constant Field Values
  - TESTS_FILE_NOT_FOUND_MESSAGE
```
private static final java.lang.String TESTS_FILE_NOT_FOUND_MESSAGE
```
    The message used if the file with the names of test files is not found.
    
    See Also:
    
    Constant Field Values
  - PRINTWRITER_ERROR_MESSAGE
```
private static final java.lang.String PRINTWRITER_ERROR_MESSAGE
```
    The error message used if a PrintWriter throws a FileNotFoundException
    
    See Also:
    
    Constant Field Values
  - IOEXCEPTION_MESSAGE
```
private static final java.lang.String IOEXCEPTION_MESSAGE
```
    The message shown if the program encounters an IOException when reading String arrays from files
    
    See Also:
    
    Constant Field Values
  - FILE_DOES_NOT_EXIST_MESSAGE
```
private static final java.lang.String FILE_DOES_NOT_EXIST_MESSAGE
```
    The message shown when a test file does not exist.
    
    See Also:
    
    Constant Field Values
  - NO_INTEGERS_MESSAGE
```
private static final java.lang.String NO_INTEGERS_MESSAGE
```
    The message shown when the file does not contain integers in the proper format.
    
    See Also:
    
    Constant Field Values
  - NO_POSSIBILITIES_MESSAGE
```
private static final java.lang.String NO_POSSIBILITIES_MESSAGE
```
    The message shown when there is no possible combination that is under the limit.
    
    See Also:
    
    Constant Field Values
  - UNIT
```
private static final java.lang.String UNIT
```
    Printed after every watermelon weight that gets added to the knapsack in knapsack.txt.
    
    See Also:
    
    Constant Field Values
  - SPACE
```
private static final java.lang.String SPACE
```
    A space.
    
    See Also:
    
    Constant Field Values
  - TAB
```
private static final java.lang.String TAB
```
    A tab.
    
    See Also:
    
    Constant Field Values
  - NEW_LINE
```
private static final java.lang.String NEW_LINE
```
    A new-line character.
    
    See Also:
    
    Constant Field Values
  - COMMA
```
private static final java.lang.String COMMA
```
    A comma.
    
    See Also:
    
    Constant Field Values
  - EMPTY_STRING
```
private static final java.lang.String EMPTY_STRING
```
    Empty string.
    
    See Also:
    
    Constant Field Values
  - output
```
private static java.io.PrintWriter output
```
    A PrintWriter field to write to the output file, which will be used in the main and other methods.
  - watermelons
```
private static java.util.List<java.lang.Integer> watermelons
```
    The list where the chosen objects for a problem are stored.
  - keyboard
```
private static java.util.Scanner keyboard
```
    A Scanner object which will be used to read user input.
- Constructor Detail
  - Knapsack
```
public Knapsack()
```
- Method Detail
  - main
```
public static void main(java.lang.String[] args)
```
  - knapsackSum
```
public static int knapsackSum(int[] w,
                              int n,
                              int limit)
```
    A method that finds the optimal sum of weights that can still fit in the knapsack recursively. Unlike the other knapsackSum method, this one does not record the items used to achieve the sum.
    
    Parameters:
    
    w - the list of weights
    
    n - the number of weights in w (this is a precondition)
    
    limit - the limit on weight of the knapsack
    
    Returns:
    
    the maximum amount of weight that can be attained with the weights provided without overloading the knapsack
  - knapsackSum
```
public static int knapsackSum(int[] w,
                              int n,
                              int limit,
                              java.util.List<java.lang.Integer> list)
```
    A method that finds the solution to the knapsack problem and remembers the items used to achieve that maximum weight without going over the limit.
    
    Parameters:
    
    w - the list of weights
    
    n - the number of weights (this is a precondition)
    
    limit - the limit on weight of the knapsack
    
    list - the list to add items that are chosen to
    
    Returns:
    
    the maximum amount of weight that can be attained with the weights provided without overloading the knapsack
  - readFileWithStringArray
```
private static java.util.ArrayList<java.lang.String> readFileWithStringArray(java.lang.String inputName)
                                                                      throws java.io.IOException
```
    An internal method that reads a file and returns its lines as a String array. Used to read the names of the test file.
    
    Parameters:
    
    inputName - the file to read the String array from
    
    Returns:
    
    an empty String array if the file does not exist or has no text, or a String array with the lines of the corresponding file to inputNam
    
    Throws:
    
    java.io.IOException - if an error occurs during the Files.readAllLines(path) method
  - readItemsFromFile
```
private static java.lang.Integer[] readItemsFromFile(java.lang.String inputName)
                                              throws java.io.FileNotFoundException
```
    An internal method that reads the integers within a file. Used to read the items from a file containing the limit and weights (the "items") to be used for the knapsack problem.
    
    Parameters:
    
    inputName - the name of the file to read the items from
    
    Returns:
    
    an int array with the items in it; if the file didn't exist or had no valid numbers, it returns an empty array
    
    Throws:
    
    java.io.FileNotFoundException - if the file with name inputName is not found
  - writeTestToFile
```
private static void writeTestToFile(java.lang.String fileName,
                                    int limit,
                                    int[] w)
```
    Writes a test class for knapsack to the file "knapsack.txt." It prints the file name, limit, and weights onto the file then prints the best combination of watermelons (the one that will attain the most weight without going over the limit by calling the second knapsack method.
    
    Parameters:
    
    fileName - the name of the test file
    
    limit - the limit contained within the designated test files
    
    w - the weights contained within the test files

Class Knapsack

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

OUTPUT_NAME

EXIT_PHRASE

ERROR_CODE

TESTS_FILE_NOT_FOUND_MESSAGE

PRINTWRITER_ERROR_MESSAGE

IOEXCEPTION_MESSAGE

FILE_DOES_NOT_EXIST_MESSAGE

NO_INTEGERS_MESSAGE

NO_POSSIBILITIES_MESSAGE

UNIT

SPACE

TAB

NEW_LINE

COMMA

EMPTY_STRING

output

watermelons

keyboard

Constructor Detail

Knapsack

Method Detail

main

knapsackSum

knapsackSum

readFileWithStringArray

readItemsFromFile

writeTestToFile