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
vi, and there are xi 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 {
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);
}
}
