Assignment

0-1 Solitaire

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.

Allowance 15

[5, 12], [10, 8], [4, 6], [5, 8] → The maximum score is 14. The cards bought are [10, 8] and [4, 6] where the final cost is 14.

Allowance 15

[5, 4], [1, 4], [2, 4], [4, 2], [2, 5], [4, 1], [2, 2] → The maximum score is 17. The cards chosen were [5, 4], [2, 4], [4, 2], [4, 1], [2, 2]. The final cost is 13.

Allowance 5

[77, 18], [68, 11], [63, 12] → The maximum score is 0. There are no cards that can be bought so the final score is 0.

Allowance 100

[96, 17], [85, 15], [87, 16], [74, 20], [62, 19], [55, 15], [65, 16], [78, 16], [97, 19], [83, 18] → The maximum score is 508. The cards bought are [96, 17], [85, 15], [87, 16], [65, 16], [78, 16], [97, 19] with the final cost of 99.

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.

Criteria

To receive maximum points for this assignment you must follow the guidelines presented here.

1. You must implement and utilize a singly linked list. The linked list must be written from scratch by you. Only implement the necessary methods that will help you solve the problem. Try to keep your linked list implementation minimal.

a. You may not use the built-in list implementations in the Java library. This includes Linked List and Array List.

b. Each node of the linked list must include only three elements: two integer types and a reference to the next element of the list. The nodes represent the cards.

c. You may not have more than one instance of a linked list.

2. Read the cards data from a file called in.txt as specified in the input section of this document. You can assume this file is in the same location as your program.

a. No calculations are permitted while reading in the data from in.txt.

b. Once the data is read into your linked list, you may not manipulate the data or the list. For example, you may not sort, shuffle, remove, or add to the list. Once the cards have been read in, the list must remain the same throughout the life of the program.

c. Your program may not modify the file at all. It should perform read-only operations.

3. No additional data structures are allowed. This includes arrays, strings, trees, etc. All computations must be done in place in the original linked list (section 2b). Your program may use auxiliary scalar variables and reference variables (used to point to nodes of the list).

a. There is only one exception to the rule and that is when you are reading in the data you may use strings. This is also the only time you may use the standard library as well. For example, you can use StringTokenizer and/or the Scanner library.

4. Bit masking is not allowed and is not a solution. Use of an array of Booleans or integers is also disallowed according to guideline 3.

5. All code should be placed in one .java file and must be able to be compiled and ran from that .java file. Inner classes are allowed. Again, try to write short and simple programs. I/O, exception handling, and the linked list implementation should be kept to a minimum.

Assignment 2 must be solved by following these guidelines. Bypassing any of these, such as saving numbers in string or using an array to keep track of additional data will be penalized. If you have any questions about what can and cannot be used, you may email me.

Your Analysis

The final part to this assignment is your analysis of the problem and your algorithm and the complexity of the problem. The report should not exceed two pages and should be in the format of an ASCII text document, MS Word document, or PDF.

NOTE: It is important that you write a description of the algorithm and not a description of your program!

You should explain

• The sequence of operations that you use to solve the problem.
• Why this sequence of operations correctly solves the problem.

o Pseudocode is a standard way to explain an algorithm.

• The complexity. (The BigO of the problem).

What you need to turn in

Once you have completed the assignment and are ready to submit you must zip all your files into a single zip archive. The extension must be .zip. The name of the .zip file must be your netID so if your netID were broge2 then the file must be named broge2.zip.

The files that must be in the zip are your .java file that contains all your code and must be compileable and runnable and must solve the problem laid out in this document. It must also contain the document file that describes your algorithm and the complexity. The name of this file is up to you.

Attachment:- Text-File.rar