Suppose we are to play a game in which we have a group of cards with 2 numbers on them. One number is how many points the card is worth, and the other number is how much the card costs. You are given a set allowance you can spend on buying cards. Once you buy a card, you are not allowed to purchase the card again. Your goal is write a program in Java called Game01 that will find the maximum score you can make with the set allowance given. You do not need to necessarily spend all the allowance, but you cannot spend more than the allowance. The program should simply print the maximum score.

Input
The input to your program is a file called in.txt. You can safely assume this file will be in the same location as your program. The format of this file is as follows.
1. The first line contains your given allowance. It is a single integer greater than or equal to 0.
2. The next N lines each contain two numbers representing the points and cost respectively.
a. The points will be random nonzero positive integer values.
b. The costs will be random nonzero positive integer values.
c. The number of cards, N, is random but there will at least be 1 card.
3. There may be duplicate cards with either the same point value and same cost or same point value and different costs.

Output
The output of your program should be a single integer that is the maximum score that can be made by purchasing cards.

Examples
The following examples are not representative of the format in.txt will have. For the format, refer to the “Input” section.
Allowance 5
[6, 2], [8, 2], [4, 2], [7, 1], [7, 1], [3, 2] ? The maximum score is 22. The cards bought are [8, 2], [7, 1], [7, 1] where the final cost is 4.
Allowance 5
[10, 1], [8, 10], [10, 3], [7, 2], [3, 2] ? The maximum score is 20. The cards bought are [10, 1], [10, 3] where the final cost is 4.

The examples presented are not the only tests that may be used to check your algorithm is correct so be sure to test with many different values for allowance, points, and costs.

Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

/**
* The Game01 program reads the
* data from the input.txt and stores the data in
* the form of a linked list.
*/
public class Game01 {

/**
* The internal node class this represents the node of the linked list.
*/
class Node{
int point;
int cost;
Node next;
}

/**
* The method takes the reference to the root of the
* linked list. It recursively computes the maximum
* point that can be purchased using the given allowance.
* @param root
* @param allowance
* @return
*/
public int knapsack(Node root, int allowance){
if(allowance == 0 || root == null){
return 0;
}...

This is only a preview of the solution. Please use the purchase button to see the entire solution

Warning: If you try using HL materials in an unethical manner, expect to fail your class. All HL items are old, recycled homework and are therefore not original. We intend them to be used only for the purposes of studying and learning.