# “`java Java编程问题，逻辑有问题 “`

go评论54阅读模式

Java programming question, issue with logic

# 问题

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

``````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];
``````

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

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

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}
...

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} *

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

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

go 55

go 47

go 51

go 47