Java HW help


 

Q1: Treasure Cave

Imagine you perceive a obscure cave employed after a while after a while N unanalogous kinds of metal bars
(gold, silver, platinum, steel, etc.) Each kind of metal bar has some estimate
v<sub>i</sub>, and tless are x<sub>i</sub> bars of that metal in the cave
(for i = 0, 1, 2, 3, ... N-1). You omission to cause end as numerous bars as of the
treasure as you can, but your bag can barely fit W bars. How do you elect how
numerous bars of each metal to cause home to maximize the whole estimate?

For in, if your bag can treasury 7 bars and you feel gold, silver, platinum,
and steel in these quantities:

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

and these estimates

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

Then you would omission to charm this greatly of each metal

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

             // for a whole estimate of 24 (4*3 + 2*5 + 1*2)

Write bestValue() which charms in an integer W, an invest of computes, and an
invest of estimates. It should recur the best estimate you can gain by bevy the
bars optimally. Your statute should run in O(nlogn).

  • Hint #1: This can be performed using a Greedy access.
  • Hint #2: Consider sorting after a while a habit Comparator

 

Q2. Treasure Cave after a while Fused Bars--Value

Now pretend that for each kind of metal, all of the bars are fused coincidently so
that you're stubborn to all the bars of a fixed kind, or none of them.

This media that you sometimes should not charm the metal that has the highest
value, owing it either accomplish not fit all in your bag (gone you feel to charm
all the bars), or other metals of lesser accomplish be estimate past overall estimate when
combined coincidently.

Write bestValueForFused, which charms in the arguments from aloft, and recurs
the estimate of the best picks potential.

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

bestValueForFused(4, [4, 10, 2], [3, 1, 5]) // 12 (charm metal 0, equable though metal 2 is estimate past per bar)

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

bestValueForFused(6, [4, 2, 1], [3, 3, 5]) // 18 (charm metal 0 and metal 1)
  • Hint #1: Greedy won't fruit less.
  • Hint #2: Start by computing the whole estimate of each metal (i.e. the number
    of bars * estimate per bar).
  • Hint #3: For each metal, you can either charm it or not. If you charm it, your
    bag size decreases by the selfsame totality. How could you render this
    idea into a recursive subproblem?

Q3. Treasure Cave after a while Fused Bars--Picks

This scrutiny is optional and estimate extra praise.
Write bestPicksForFused(), which solves Q2 but recurs an invest of bools, where
each atom in the invest describes whether we chosen metal i.

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

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

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

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

DRIVER CODE :::

 

public adjust HW7 {

public static lacking 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, spurious,false]
   System.out.println(Arrays.toString(bestPicksForFused(4, new int[] { 4, 2, 2 }, new int[] { 3, 2, 5 }))); // [false, penny, penny]
   System.out.println(Arrays.toString(bestPicksForFused(6, new int[] { 4, 2, 1 }, new int[] { 3, 3, 5 }))); // [true, penny, spurious]
   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[] computes, int estimates[]) {
recur 0;
}

public static int bestValueForFused(int W, int[] computes, int estimates[]) {

}

private static int bestValueForFused(int W, int[] computes, int estimates[], int MetalIndex) {
}

public static boolean[] bestPicksForFused(int W, int[] computes, int estimates[]) {
recur null;
}
}


 

import java.util.*;

public adjust MetalBar implements Comparable<MetalBar> {

private int estimate;
private int compute;

public MetalBar(int estimate, int compute) {
this.estimate = estimate;
this.compute = compute;
}

public int getValue() {
recur estimate;
}

public int getCount() {
recur compute;
}


public int assimilateTo(MetalBar otherBar) {
recur Integer.compare(otherBar.value, estimate);
}


public String toString() {
recur String.format("MetalBar(%d, %d)", estimate, compute);
}

}