java - 查找达到给定值的最小包装数

Question

我正在尝试解决与此问题类似的问题，但进行了一些修改:

“给定一个值 V，如果我们想要找 V 分，并且我们有无限供应的每个 C = { C1, C2, .. , Cm} 值(value)的硬币，那么最小数量是多少硬币来找零吗？”

Input: coins[] = {25, 10, 5}, V = 30

Output: Minimum 2 coins required

We can use one coin of 25 cents and one of 5 cents

就我而言，我有一个对象数组，而不仅仅是一个数字数组。在每个对象中我都有一个数量和价格。 我想打印形成给定数量的最小对象数量，然后打印价格，例如:

2 x 5 9.95

1 x 3 5.95

我找到了这段代码，但我找不到如何完成任务:

public static void main(String[] args) {
        Product croissant = new Product("Croissant", "CF", null);

        Pack CF_1 = new Pack(3, 5.95);
        Pack CF_2 = new Pack(5, 9.95);
        Pack CF_3 = new Pack(9, 16.99);
        croissant.addPack(CF_1);
        croissant.addPack(CF_2);
        croissant.addPack(CF_3);

        System.out.println(minCoins(croissant, 13));
    }

    static int minCoins(Product product, int V) {
        // table[i] will be storing
        // the minimum number of coins
        // required for i value. So
        // table[V] will have result
        int table[] = new int[V + 1];

        // Base case (If given value V is 0)
        table[0] = 0;

        // Initialize all table values as Infinite
        for (int i = 1; i <= V; i++)
            table[i] = Integer.MAX_VALUE;

        // Compute minimum coins required for all
        // values from 1 to V
        for (int i = 1; i <= V; i++) {
            // Go through all coins smaller than i
            for (Pack pack : product.packList) {
                if (pack.qty <= i) {
                    int sub_res = table[i - pack.qty];
                    if (sub_res != Integer.MAX_VALUE
                            && sub_res + 1 < table[i])
                        table[i] = sub_res + 1;
                }
            }
        }
        return table[V];
    }

Answer 1

您可以获得贡献最低金币的包列表，如下所示:

您从给定的 V 开始，然后查找表中值小于 1 的包，因为要达到 V > 你一定在某个地方有一个小于 1 的值。如果您找到了一个，请将其添加到列表中，然后将下一个 V 减去您找到的包的数量，然后继续。

代码是:

   void printList(int[] table, Product product, int V) {
      List<Pack> list = new ArrayList<>();
      if ( table[V] == Integer.MAX_VALUE ) return list;
      while ( V > 0 ) {
        for (Pack pack : product.packList) {
          if ( V >= pack.qty && table[V-pack.qty] == table[V] - 1 ) {
            list.add(pack);
            V = V-pack.qty;
            break;
          }
        }
      }
    }

对于 V = 13 的示例，列表将为: [{3, 5.95}, {5, 9.95}, {5, 9.95}] 假设您将 Pack 类的 toString() 实现为:

public String toString() {
  return "{" + this.qty + "," + this.price + "}";
}

如果您想使用Collectors，您可以将列表缩小为 map 。

类似于:list.stream().collect(Collectors.groupingBy(Pack::getQty))