2(a). Use the CoinRow algorithm from the book to find the maximum value of coins

Question

2(a). Use the CoinRow algorithm from the book to find the maximum value of coins to select from the row of coins: 25, 5, 5, 10, 1, 25.

(b). Use the robot coin collecting algorithm to find the maximum number of coins in a 5 by 7 table, where coins are at the (row,column) coordinates: (1, 2), (1, 5), (2, 1), (2, 4), (2, 7), (3, 4), (3,6), (4, 2), (4, 7), (5, 3), (5, 5).

(c). Use the textbook's knapsack algorithm to find the solution for the following knapsack problem: sack with capacity 10, and objects O1 with weight 1, value 30; O2 with weight 7 value 100; O3 with weight 3 value 50; O4 with weight 5 value 30; O5 with weight 6 value 40

Explanation / Answer

public class CoinRow {

public static void main(String[] args) {
int[] coins = { 25, 5, 5, 10, 1, 25};
System.out.println(maxValue(coins));// calling maxvalue function
}
  
  
   public static int maxValue(int[] coins) {// returns maximum value
assert coins.length > 0 : "no coins to select";

int[] coinsArray = new int[coins.length + 1];// declaring
for (int i = 0; i < coins.length; i++) {
coinsArray[i + 1] = coins[i];// make room at first place
}

int[] found = new int[coins.length + 1];// after collecting coins max value stored found array
found[0] = 0;
found[1] = coinsArray[1];// first coin is assaining to found array of index 1

for (int i = 2; i <= coins.length; i++) {// finding max value in the loop calling max function it retuns max value
found[i] = max(coinsArray[i] + found[i - 2], found[i - 1]);
}
return found[coins.length];// retuns coins length
}

private static Integer max(int i, int j) {
return i > j ? i : j;
}

}

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.