Home » Java hw help | Computer Science homework help

Java hw help | Computer Science homework help

 

Q1: Treasure Cave

Imagine you find a hidden cave filled with with N different types of metal bars
(gold, silver, platinum, steel, etc.) Each type of metal bar has some value
v<sub>i</sub>, and there are x<sub>i</sub> bars of that metal in the cave
(for i = 0, 1, 2, 3, … N-1). You want to bring back as many bars as of the
treasure as you can, but your bag can only fit W bars. How do you choose how
many bars of each metal to bring home to maximize the total value?

For example, if your bag can store 7 bars and you have gold, silver, platinum,
and steel in these quantities:

[4, 10, 2, 4] // 4 bars of gold, 10 silver, 2 platinum, 4 steel

and these values

[3, 1, 5, 2]  // gold worth 3 per bar, silver worth 1, platinum 5, steel 2

Then you would want to take this much of each metal

[4, 0, 2, 1]  // all the gold, no silver, all the platinum, 1 steel bar

             // for a total value of 24 (4*3 + 2*5 + 1*2)

Write bestValue() which takes in an integer W, an array of counts, and an
array of values. It should return the best value you can earn by picking the
bars optimally. Your code should run in O(nlogn).

  • Hint #1: This can be done using a Greedy approach.
  • Hint #2: Consider sorting with a custom Comparator

 

Q2. Treasure Cave with Fused Bars–Value

Now assume that for each type of metal, all of the bars are fused together so
that you’re forced to all the bars of a certain type, or none of them.

This means that you sometimes should not take the metal that has the highest
value, because it either will not fit all in your bag (since you have to take
all the bars), or other metals of lesser will be worth more overall value when
combined together.

Write bestValueForFused, which takes in the arguments from above, and returns
the value of the best picks possible.

bestValueForFused(4, [], []) // 0 (the cave is empty)

bestValueForFused(4, [4, 10, 2], [3, 1, 5]) // 12 (take metal 0, even though metal 2 is worth more per bar)

bestValueForFused(4, [4, 2, 2], [3, 2, 5]) // 14 (take metal 1 and metal 2)

bestValueForFused(6, [4, 2, 1], [3, 3, 5]) // 18 (take metal 0 and metal 1)

  • Hint #1: Greedy won’t work here.
  • Hint #2: Start by computing the total value of each metal (i.e. the number
    of bars * value per bar).
  • Hint #3: For each metal, you can either take it or not. If you take it, your
    bag capacity decreases by the corresponding amount. How could you translate this
    idea into a recursive subproblem?

Q3. Treasure Cave with Fused Bars–Picks

This question is optional and worth extra credit.
Write bestPicksForFused(), which solves Q2 but returns an array of bools, where
each element in the array describes whether we picked metal i.

bestPicksForFused(4, [], []) // []

bestValueForFused(4, [4, 10, 2], [3, 1, 5]) // [true, false, false]

bestValueForFused(4, [4, 2, 2], [3, 2, 5]) // [false, true, true]

bestValueForFused(6, [4, 2, 1], [3, 3, 5]) // [true, true, false]

DRIVER CODE :::

 

public class HW7 {

public static void main(String[] args) {
// Q1
   System.out.println(bestValue(7, new int[] {}, new int[] {})); // 0
   System.out.println(bestValue(7, new int[] { 4 }, new int[] { 1 })); // 4
   System.out.println(bestValue(7, new int[] { 4, 10, 2, 4 }, new int[] { 3, 1, 5, 2 })); // 24 [5,3,2,1] //24
   System.out.println(bestValue(7, new int[] { 4, 10, 2, 4 }, new int[] { 3, 3, 5, 2 })); // 25
   System.out.println(bestValue(7, new int[] { 4, 10, 2, 4 }, new int[] { 3, 5, 5, 2 })); // 35

// Q2
   System.out.println(bestValueForFused(4, new int[] {}, new int[] {})); // 0
   System.out.println(bestValueForFused(4, new int[] { 4 }, new int[] { 1 })); // 4
   System.out.println(bestValueForFused(4, new int[] { 4, 10, 2 }, new int[] { 3, 1, 5 })); // 12
   System.out.println(bestValueForFused(4, new int[] { 4, 2, 2 }, new int[] { 3, 2, 5 })); // 14
   System.out.println(bestValueForFused(6, new int[] { 4, 2, 1 }, new int[] { 3, 3, 5 })); // 18
   System.out.println(bestValueForFused(6, new int[] { 4, 2, 1 }, new int[] { 3, 2, 9 })); // 21 (3*4+9*1)

// Q3
   System.out.println(Arrays.toString(bestPicksForFused(4, new int[] {}, new int[] {}))); // []
   System.out.println(Arrays.toString(bestPicksForFused(4, new int[] { 4 }, new int[] { 1 }))); // [true]
   System.out.println(Arrays.toString(bestPicksForFused(4, new int[] { 4, 10, 2 }, new int[] { 3, 1, 5 }))); // [true, false,false]
   System.out.println(Arrays.toString(bestPicksForFused(4, new int[] { 4, 2, 2 }, new int[] { 3, 2, 5 }))); // [false, true, true]
   System.out.println(Arrays.toString(bestPicksForFused(6, new int[] { 4, 2, 1 }, new int[] { 3, 3, 5 }))); // [true, true, false]
   System.out.println(Arrays.toString(bestPicksForFused(6, new int[] { 4, 2, 1 }, new int[] { 3, 2, 9 }))); // [true,false,true]

}

public static int bestValue(int W, int[] counts, int values[]) {
return 0;
}

public static int bestValueForFused(int W, int[] counts, int values[]) {

}

private static int bestValueForFused(int W, int[] counts, int values[], int MetalIndex) {
}

public static boolean[] bestPicksForFused(int W, int[] counts, int values[]) {
return null;
}
}

 

import java.util.*;

public class MetalBar implements Comparable<MetalBar> {

private int value;
private int count;

public MetalBar(int value, int count) {
this.value = value;
this.count = count;
}

public int getValue() {
return value;
}

public int getCount() {
return count;
}

public int compareTo(MetalBar otherBar) {
return Integer.compare(otherBar.value, value);
}

public String toString() {
return String.format(“MetalBar(%d, %d)”, value, count);
}

}

Calculate the price of your order

550 words
We'll send you the first draft for approval by September 11, 2018 at 10:52 AM
Total price:
$26
The price is based on these factors:
Academic level
Number of pages
Urgency
Basic features
  • Free title page and bibliography
  • Unlimited revisions
  • Plagiarism-free guarantee
  • Money-back guarantee
  • 24/7 support
On-demand options
  • Writer’s samples
  • Part-by-part delivery
  • Overnight delivery
  • Copies of used sources
  • Expert Proofreading
Paper format
  • 275 words per page
  • 12 pt Arial/Times New Roman
  • Double line spacing
  • Any citation style (APA, MLA, Chicago/Turabian, Harvard)

Our guarantees

Delivering a high-quality product at a reasonable price is not enough anymore.
That’s why we have developed 5 beneficial guarantees that will make your experience with our service enjoyable, easy, and safe.

Money-back guarantee

You have to be 100% sure of the quality of your product to give a money-back guarantee. This describes us perfectly. Make sure that this guarantee is totally transparent.

Read more

Zero-plagiarism guarantee

Each paper is composed from scratch, according to your instructions. It is then checked by our plagiarism-detection software. There is no gap where plagiarism could squeeze in.

Read more

Free-revision policy

Thanks to our free revisions, there is no way for you to be unsatisfied. We will work on your paper until you are completely happy with the result.

Read more

Privacy policy

Your email is safe, as we store it according to international data protection rules. Your bank details are secure, as we use only reliable payment systems.

Read more

Fair-cooperation guarantee

By sending us your money, you buy the service we provide. Check out our terms and conditions if you prefer business talks to be laid out in official language.

Read more