Question

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.

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

/**
* 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

Assisting Tutor

Related Homework Solutions

Java Programming Problems
Homework Solution
$45.00
Computer Science
Java Programming
Palindromes
Arrays
Integers
Pairs
Strings
Loops
Recursion
Arguments
Exceptions
Constructors
Classes
Static Variables
Person Class in Java
Homework Solution
$5.00
Computer Science
Java Programming
Person Class
Strings
Constructors
Methods
Mutators
Statements
Variables
Circular Queue of Strings in Java
Homework Solution
$10.00
Computer Science
Java Programming
Circular Queue
Data
Numbers
Strings
Linked Lists
Lines
Statements
Entries
Tree Data Structures in Java
Homework Solution
$23.00
Computer Science
Java Programming
Data Structures
Programming Skills
Phylogenetic Trees
Species
Interfaces
Array List
Strings
Arbitrary Order
Track and Trace in Pharmaceutical Industries
Homework Solution
$10.00
Computer Science
Java Programming
Track
Trace
Pharmaceutical Industries
Barcodes
Batches
Companies
Departments
Compounding
Pills
Statements
Variables
Algorithms
Accounting Problems in Java
Homework Solution
$20.00
Computer Science
Java Programming
Accounting
Classes
Interest Rates
Funds
Withdrawals
Savings
Data Fields
Initial Balance
Constructors
Get help from a qualified tutor
Live Chats