Java编程问题，逻辑问题
最近我遇到了一个编程问题，比如，给定一个总数和一个输入k，找出我们可以用从1到k的数字达到总数的总次数。
例如: total = 5，k=3
输出应为5
因为我们可以通过5种方式使用1，2和3来达到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;
}任何帮助都是非常感谢的。
回答 2
Stack Overflow用户
发布于 2020-07-30 23:10:22
这是一个经典的问题，可以通过动态编程轻松解决。另请参阅类似的问题：https://en.wikipedia.org/wiki/Change-making_problem
第一个观察结果是，当您尝试编写数字不超过k的total时，可以使用k，也可以不使用k。
如果你使用k，那么你仍然需要使total - k的数字达到k。如果你不使用k，那么你就可以有效地使数字达到k-1的total。
如果我们称total为使总数达到k的方法的数量，那么我们的观察给出了一个公式：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 > 0的c[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，根据评论
Stack Overflow用户
发布于 2020-07-30 20:33:35
以你的示例total = 5，k= 3为例，问题是找到一个函数"f(k，total)“，它将尝试从1到k的所有值"v”，以求和为" total“减去"v”。
f(3, 5) then does:
"f" tries 1 and must now sum to 4 i.e. calls f(3, 4)
"f" tries 2 and must now sum to 3 i.e. calls f(3, 3)
"f" tries 3 and must now sum to 2 i.e. calls 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 to 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("add a copy of the current stack to your solutions.");
return;
}
for (int v = 1; v <= Math.min(k, total); ++v) {
f(v, total - v);
}
} https://stackoverflow.com/questions/63171189
复制相似问题
腾讯云开发者
