背包问题用递归，如何实现

import java.util.*;

public class HW8 {

  public static void main(String[] args) {
    // Q1
    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)
}
 public static int bestValueForFused(int B, int[] counts, int values[]) {
     int num=counts.length;
    if(num == 0){
      return 0;
    }
    else if(num<=1){
      return counts[0];
    }
    else {
      int max1 = values[num];
      int max2 = values[num] + bestValueForFused(B-counts[num-1],counts,values);
      return Math.max(max1,max2);
    }
  } 

}

我只想知道如何使用---递归---实现背包问题选取最佳值。背包容量，矿石个数，矿石价值。只能选取整份矿石

 

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.

写下BestValueForFusion，包的大小、所有金属的计数和所有金属的值，并返回可能的最佳价值。

现在假设对于每种类型的金属，所有的金属条都熔合在一起，这样你就被迫使用某一类型的所有金属条，或者不使用。

这意味着你有时不应该拿价值最高的金属，因为它要么不能放在你的包里（因为你必须拿所有的金属条），要么其他价值较低的金属在一起时价值更高。

比如：

(4, new int[] {4, 10, 2}, new int[] {3, 1, 5})); // 12（4，10，2是个数）（3，1，5是价值）（4是背包容量）

所以4*3=12

需求描述不是很明确，可以再梳理一下需求吗？

你好，我是有问必答小助手。为了技术专家团更好地为您解答问题，烦请您补充下（1）问题背景详情，（2）您想解决的具体问题，（3）问题相关代码图片或者报错信息。便于技术专家团更好地理解问题，并给出解决方案。

您可以点击问题下方的【编辑】，进行补充修改问题。

您好，我是有问必答小助手，你的问题已经有小伙伴为您解答了问题，您看下是否解决了您的问题，可以追评进行沟通哦~

如果有您比较满意的答案 / 帮您提供解决思路的答案，可以点击【采纳】按钮，给回答的小伙伴一些鼓励哦～～

ps:问答VIP仅需29元，即可享受5次/月 有问必答服务，了解详情>>>https://vip.csdn.net/askvip?utm_source=1146287632

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);
}

}