“`java Java编程问题,逻辑有问题 “`

huangapple go评论69阅读模式
英文:

Java programming question, issue with logic

问题

最近我遇到了一个编程问题,要求给定一个总数和一个输入的k值,找出用从1到k的数字达到总数的方法总数。

例如:总数为5,k为3

输出应该为5

因为我们可以使用1、2和3有5种方式达到5,如下所示:

1+1+1+1+1

1+1+1+2

1+2+2

1+1+3

2+3

我已经提出了下面的逻辑,但它不完全有效,因为我没有进行回溯(我猜),我不确定如何做

private static int totalways(int total, int k) {
    List<Integer> arr = new ArrayList();
    for (int i = 0; i < total; i++) {
        arr.add(1);
    }
    int count = 1;
    boolean breakLoop = true;
    while (breakLoop) {
        int last = arr.size() - 1;
        for (int i = last; i >= 1; i--) {
            if (arr.get(i) + arr.get(i - 1) <= k) {
                count++;
                int sum = arr.get(i) + arr.get(i - 1);
                arr.remove(i - 1);
                arr.remove(i - 1);
                arr.add(sum);
            }
        }
        if (arr.size() == 2) {
            breakLoop = false;
        }
    }
    return count;
}

任何帮助都会感激。

英文:

Recently I came across a programming question like, given a total and an input k find the total number of ways we can reach total with numbers from 1 to k.

for eg: total = 5, k = 3

the output should be 5

cause we can reach 5 in 5 ways using 1, 2 and 3 as below

1+1+1+1+1

1+1+1+2

1+2+2

1+1 +3

2 + 3

I have come up with the below logic, but it's not completely working as am not doing backtracking (I suppose) which I am not sure on how to do

private static int totalways(int total, int k) {
        List&lt;Integer&gt; arr =  new ArrayList();
        for (int i=0; i&lt;total; i++) {
            arr.add(1);
        }
        int count = 1;
        boolean breakLoop = true;
        while (breakLoop) {
            int last = arr.size()-1;
            for (int i=last; i&gt;=1; i--) {
                if (arr.get(i) + arr.get(i-1) &lt;= k) {
                    count++;
                    int sum = arr.get(i) + arr.get(i-1);
                    arr.remove(i-1);
                    arr.remove(i-1);
                    arr.add(sum);
                }
            }
            if (arr.size() == 2){
                breakLoop = false;
            }
        }
        return count;
    }

Any help is appreciated.

答案1

得分: 2

这是一个经典问题,可以轻松通过动态规划来解决。还可以参考类似的问题:https://en.wikipedia.org/wiki/Change-making_problem

首先观察到,当您试图用不超过 k 的数字来表示 total 时,可以选择使用 k,或者不使用 k

如果使用 k,那么您仍然需要使用不超过 k 的数字来组成 total - k。如果不使用 k,那么实际上是在使用不超过 k-1 的数字组成 total

如果我们将 c[total][k] 表示为使用不超过 k 的数字组成 total 的方式数,那么我们的观察得出以下公式:c[total][k] = c[total-k][k] + c[total][k-1]

编辑:这个公式仅在 k <= total 时成立。如果 k > total,则 c[total][k] = c[total][k-1]

我们还可以观察到,对于所有 k 的值,c[0][k] = 1,对于任何 total > 0c[total][0] = 0

编写一个使用递归公式的朴素递归程序将会很糟糕;因为对于每个调用,我们需要进行两次递归调用,这将导致指数级的复杂度。

相反,我们可以在动态规划算法中使用我们的公式,只需填充一个二维数组 c[][] 来存储结果:

int[][] c = new int[total+1][k+1];
for (int n = 1; n <= total; ++n)
{
  c[n][0] = 0;
}
for (int j = 0; j <= k; ++j)
{
  c[0][j] = 1;
}
for (int n = 1; n <= total; ++n)
{
  int maxj = (k <= n) ? k : n;         // maxj = min(k,n)
  for (int j = 1; j <= maxj; ++j)      // case j <= n
  {
    c[n][j] = c[n-j][j] + c[n][j-1];
  }
  for (int j = maxj + 1; j <= k; ++j)  // case j > n
  {
    c[n][j] = c[n][j-1];
  }
}
return c[total][k];

编辑:考虑到情况 k > total,根据评论进行修改。

英文:

This is a classic problem that can easily be solved with dynamic programming. See also this similar problem: https://en.wikipedia.org/wiki/Change-making_problem

The first observation is that when you're trying to write total with numbers up to k, you can either use k, or not use k.

If you use k, then you still have to make total - k with numbers up to k. If you don't use k, then you're effectively making total with numbers up to k-1.

If we call c[total][k] the number of ways to make total with numbers up to k, then our observation gives us a formula: c[total][k] = c[total-k][k] + c[total][k-1].

EDIT: This formula is true iff k &lt;= total. If k &gt; total, then c[total][k] = c[total][k-1].

We can also observe that c[0][k] = 1 for all values of k, and c[total][0] = 0 for any total &gt; 0.

Writing a naive recursive program to use our recursive formula would be horrible; we'd end up with an exponential complexity because for every call we need to make two recursive calls.

Instead, we can use our formula in a dynamic programming algorithm, simply filling a two-dimensional array c[][] with the results:

int[][] c = new int[total+1][k+1];
for (int n = 1; n &lt;= total; ++n)
{
  c[n][0] = 0;
}
for (int j = 0; j &lt;= k; ++j)
{
  c[0][j] = 1;
}
for (int n = 1; n &lt;= total; ++n)
{
  int maxj = (k &lt;= n) ? k : n;         // maxj = min(k,n)
  for (int j = 1; j &lt;= maxj; ++j)      // case j &lt;= n
  {
    c[n][j] = c[n-j][j] + c[n][j-1];
  }
  for (int j = maxj + 1; j &lt;= k; ++j)  // case j &gt; n
  {
    c[n][j] = c[n][j-1];
  }
}
return c[total][k];

EDIT: taking into account the case k &gt; total, as per comments

答案2

得分: 1

以下是翻译好的内容:

取您的示例,total = 5,k = 3,问题是找到一个名为"f(k, total)"的函数,该函数将尝试所有值"v"从1到k以使总和等于"total"减去"v"。

f(3, 5) 然后执行:
"f" 尝试 1,现在必须总和为 4,即调用 f(3, 4)
"f" 尝试 2,现在必须总和为 3,即调用 f(3, 3)
"f" 尝试 3,现在必须总和为 2,即调用 f(3, 2)

请注意,函数 f 调用了自身。这被称为递归调用。递归调用通常是需要回溯时的简单解决方案。

这将生成一个呼叫树,如下所示:

f(3, 5) {}
f(3, 4) {1}
f(3, 3) {1, 1}
f(3, 2) {1, 1, 1}
f(3, 1) {1, 1, 1, 1}
f(3, 0) {1, 1, 1, 1, 1} *
f(3, 0) {1, 1, 1, 2} *
f(3, 1) {1, 1, 2}
f(3, 0) {1, 1, 2, 1} *
f(3, 0) {1, 1, 3}
...

当"total"参数为0时,调用过程停止。

这个解决方案生成了相同的组合 {1,1,1,2},{1,1,2,1}... 要修复这个问题,您可以修改 f 的逻辑,以便您永远不会尝试一个比您的父调用者尝试的值 "v" 更高的值。您的函数逻辑将是:

f(k, total) {
...
for v in 1 到 min(k, total) {
...
f(v, total - v)
}
}

新的完整呼叫树将如下所示:

f(3, 5) {}
f(1, 4) {1}
f(1, 3) {1, 1}
f(1, 2) {1, 1, 1}
f(1, 1) {1, 1, 1, 1}
f(1, 0) {1, 1, 1, 1, 1} *
f(2, 3) {2}
f(1, 2) {2, 1}
f(1, 1) {2, 1, 1}
f(1, 0) {2, 1, 1, 1} *
f(2, 1) {2, 2}
f(1, 0) {2, 2, 1} *
f(3, 2) {3}
f(1, 1) {3, 1}
f(1, 0) {3, 1, 1} *
f(2, 0) {3, 2} *

现在,您只需在 total 达到0时累积找到的解决方案。

为此,您将需要某种类型的堆栈,将当前解决方案添加到其中。

void f(int k, int total) {
if (total == 0) {
System.err.println("将当前堆栈的副本添加到您的解决方案。");
return;
}
for (int v = 1; v <= Math.min(k, total); ++v) {
f(v, total - v);
}
}

英文:

Taking your example, total = 5, k = 3, the problem is to find a function "f(k, total)" that will try all values "v" from 1 to k to sum to a total that is "total" minus "v".

f(3, 5) then does:
&quot;f&quot; tries 1 and must now sum to 4 i.e. calls f(3, 4)
&quot;f&quot; tries 2 and must now sum to 3 i.e. calls f(3, 3)
&quot;f&quot; tries 3 and must now sum to 2 i.e. calls f(3, 2)

Notice that function f calls itself. This is called a recursive call. Recursive calls are generally simple solutions when you need backtracking.

This will generate a call tree like:

f(3, 5) {}
    f(3, 4) {1}
        f(3, 3) {1, 1}
            f(3, 2) {1, 1, 1}
                f(3, 1) {1, 1, 1, 1}
                    f(3, 0) {1, 1, 1, 1, 1} *
                f(3, 0) {1, 1, 1, 2} *
            f(3, 1) {1, 1, 2}
                f(3, 0) {1, 1, 2, 1} *
            f(3, 0) {1, 1, 3}
...

The calling process stops when the "total" parameter is 0.

This solution generates identical combinations {1,1,1,2}, {1,1,2,1}... To fix this, you could modify the f logic so that you could never try a value "v" higher than what your parent caller tried. Your function logic would be:

f(k, total) {
    ...
    for v in 1 to min(k, total) {
        ...
        f(v, total - v)
    }
} 

The new complete call tree would be:

f(3, 5) {}
    f(1, 4) {1}
        f(1, 3) {1, 1}
            f(1, 2) {1, 1, 1}
                f(1, 1) {1, 1, 1, 1}
                    f(1, 0) {1, 1, 1, 1, 1} *
    f(2, 3) {2}
        f(1, 2) {2, 1}
            f(1, 1) {2, 1, 1}
                f(1, 0) {2, 1, 1, 1} *
        f(2, 1) {2, 2}
            f(1, 0) {2, 2, 1} *
    f(3, 2) {3}
        f(1, 1) {3, 1}
            f(1, 0) {3, 1, 1} *
        f(2, 0) {3, 2} *

All you have to do now is accumulate the found solutions when total gets to 0.

To do this you will need some type of stack to which you will add the current solution.

void f(int k, int total) {
    if (total == 0) {
        System.err.println(&quot;add a copy of the current stack to your solutions.&quot;);
        return;
    }
    for (int v = 1; v &lt;= Math.min(k, total); ++v) {
        f(v, total - v);
    }
} 

huangapple
  • 本文由 发表于 2020年7月30日 18:24:47
  • 转载请务必保留本文链接:https://go.coder-hub.com/63171189.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定