打印您可以支付所描述金额的方式数量

Question

1元、2元、5元面值的N元有多少种支付方式

1元硬币的个数总是大于2元硬币的个数，2元硬币的个数总是大于5元硬币的个数。
注意：每种面额至少应提供一枚硬币。
限制条件 1 <= N <= 100

我尝试过类似的方法，但无法了解如何检查约束

    private static void numberOfWays(int number) {
    int one = 0, two = 0;
    int five = (number - 4) / 5;
    if (((number - 5 * five) % 2) == 0)
      {
    one = 2;
      }
    else
      {
    one = 1;
      }
    two = (number - 5 * five - one) / 2;
    System.out.println (one + two + five);
    System.out.println (five);
    System.out.println (two);
    System.out.println (one);}

Answer 1

约束很有趣。

“每个面额至少应给出一枚硬币”意味着N < 7没有解决方案。

“1元硬币的个数总是大于2元硬币的个数，2元硬币的个数总是大于5元硬币的个数”的意思是numFives = 1,numTwos = 2 , 和 numOnes = 3 开始，所以 N < 12.

没有解决方案

这满足两个约束。

知道了，你打算怎么攻打它？蛮力？

这听起来像是 knapsack problem 的变体。也许你可以读一读。

我认为 simplex method 带约束的动态规划是你最好的选择。

Answer 2

您可以尝试这样的操作：

IntStream.rangeClosed(1, 100).forEach(target -> {

    final int max1 = (target + 1 - 1) / 1;
    final int max2 = (target + 2 - 1) / 2;
    final int max5 = (target + 5 - 1) / 5;

    IntStream        .rangeClosed(         1, max5).forEach(count5 -> {
        IntStream    .rangeClosed(count5 + 1, max2).forEach(count2 -> {
            IntStream.rangeClosed(count2 + 1, max1).forEach(count1 -> {

                final int sum = count5*5 + count2*2 + count1*1;

                if (sum == target) {
                    System.out.println("Target.: " + target + " -> " + count5 + "*5$ " + count2 + "*2$ " + count1 + "*1$");
                }
            });
        });
    });
    System.out.println();
});

...但是，正如其他人所指出的那样，您的限制使得某些数量的解决方案是不可能的。

这是这个主题的变体，为所有 N...

提供了解决方案

IntStream.rangeClosed(1, 100).forEach(target -> {

    final int max1 = (target + 1 - 1) / 1;
    final int max2 = (target + 2 - 1) / 2;
    final int max5 = (target + 5 - 1) / 5;

    for         (int count1=         max1;              count1 > 0; count1--) {
        for     (int count2=Math.min(max2, count1 - 1); count2 > 0; count2--) {
            for (int count5=Math.min(max5, count2 - 1); count5 > 0; count5--) {

                final int sum = count5*5 + count2*2 + count1*1;

                if (sum == target) {
                    System.out.println("Target..............: " + target + " -> " + count5 + "*5$ " + count2 + "*2$ " + count1 + "*1$");
                    return; // Note.: solution found, exit from Consumer, NOT Method!
                }
            }
        }
    }
    /*
     * Fallback 1: at least one of each denomination...
     */
    for         (int count1=max1; count1 > 0; count1--) {
        for     (int count2=max2; count2 > 0; count2--) {
            for (int count5=max5; count5 > 0; count5--) {

                final int sum = count5*5 + count2*2 + count1*1;

                if (sum == target) {
                    System.out.println("Target (fallback 1).: " + target + " -> " + count5 + "*5$ " + count2 + "*2$ " + count1 + "*1$");
                    return; // Note.: solution found, exit from Consumer, NOT Method!
                }
            }
        }
    }
    /*
     * Fallback 2: "anything goes"...
     */
    for         (int count1=max1; count1 >= 0; count1--) {
        for     (int count2=max2; count2 >= 0; count2--) {
            for (int count5=max5; count5 >= 0; count5--) {

                final int sum = count5*5 + count2*2 + count1*1;

                if (sum == target) {
                    System.out.println("Target (fallback 2).: " + target + " -> " + count5 + "*5$ " + count2 + "*2$ " + count1 + "*1$");
                    return; // Note.: solution found, exit from Consumer, NOT Method!
                }
            }
        }
    }
    System.out.println("Target..............: " + target + " NO Solution possible!");
});

打印您可以支付所描述金额的方式数量

Print the number of ways in which you can pay the amount as described

java

math

logic

reasoning