想不通这个算法的通用名叫什么？

Question

我刚刚做了一个 Top Coder SRM，其中有一个问题我无法解决。我正在尝试在线搜索算法的详细信息，但我似乎无法找到它。

问题围绕着以下几行：你有一个数组，例如 [12, 10, 4]

每一轮，您可以应用 9,3,1 的任意排列从 [12,10,4]

中减去

Return 数组中所有数字达到 0 所需应用的最小排列数。

有什么帮助吗？

编辑：让我稍微描述一下，以便更好地理解问题。

One question would be
input: [12 10 4]
output: 2 (minimum rounds)

How it would work:
[12 10 4] - [9 3 1] = [3 7 3]
[12 10 4] - [9 1 3] = [3 9 1]
[12 10 4] - [3 9 1] = ..
[12 10 4] - [3 1 9] = ..
[12 10 4] - [1 3 9] =
[12 10 4] - [1 9 3] =

[3 7 3] - [3 9 1] = ...

..
[9 1 3] - [9 1 3] = [0 0 0] <-- achieved with only two permutation subtractions

编辑 2：

这里是 topcoder 问题： http://community.topcoder.com/stat?c=problem_statement&pm=13782

编辑3：任何人都可以解释重叠子问题和最优子结构，如果他们认为解决方案是动态规划的话？

Answer 1

编辑：

在看到原始问题后，这里是为上述问题 link 中提供的每个测试用例提供正确输出的解决方案，如果你想输入 {60}，你应该给出{60,0,0} .

基本思路是，你需要让它们最后都小于或等于零，所以如果数字可以被 3 整除，你可以通过减去 9 或 3 得到零，如果不能整除，减去 1 到使其能被 3

整除

首先，对给定的三元组进行排序，然后

检查最大数是否能被3整除，如果是，减去9仍能被3整除
现在检查下一个最大的数，如果它能被 3 整除，则减去 3，否则减去 1
如果最大数不能被3整除，减去1使其可以被3整除
现在将下一个最大的数减去 9，将另一个数减去 3

这里是实现

#include <iostream>
#include <algorithm>
#include<cmath>
using namespace std;
int f(int* a,int k){
sort(a,a+3);
if(a[2]<=0 )
{cout << k<< endl ;
return 0;}

if(a[1]<=0){
cout << k+ceil((double)a[2]/9) << endl;
return 0;

}
if(a[2]%3==0 ){
a[2]=a[2]-9;
if(a[1]%3==0 )
{
    a[1] = a[1] -3;
    a[0] = a[0] -1;
}
else{
    if(a[2]%2==0 && (a[1]-1)%2==0  && a[1]!=0){
        a[2]=a[2] +9 -3;
        a[1] = a[1] -9;
        a[0] = a[0]-1;
    }
    else{
    a[1] = a[1] -1;
    a[0] = a[0] - 3;}
}
return f(a,++k);
}
else{
a[2] = a[2] -1;

    a[1] = a[1] -9;
    a[0]=a[0] -3;
return f(a,++k);

}
}
int main() {

int a[] = {54,18,6};
f(a,0);
return 0;
}

希望对您有所帮助

示例： 输入是 [12,4,10]

排序 [12,4,10] -> [12,10,4]

现在检查最大数是否能被 3 整除，这里 Yes

所以 [12-9,10,4] -> [3,10,4] 现在检查可被 3 整除的下一个最大数，此处 N0

所以 [3,10-1,4-3] ->[3,9,1]

现在增加计数并将其传递给函数 (recursive)

输入 -> [3,9,1]

排序[3,9,1] -> [9,3,1]

现在检查最大数是否能被 3 整除，这里 Yes

所以[9-9,3,1] -> [0,3,1]

现在检查可被 3 整除的下一个最大数，此处 Yes

所以[0,3-3,1-1] -> [0,0,0]

现在增加计数并传递数组

因为最大的元素是 0 ，我们将打印计数，即 2

Answer 2

设元素个数为n，设p₁到p_n!为数组的排列你想减去，让 A 成为你的原始数组。那么你想要线性系统的自然数解

A - k₁*p₁ - ... - k_n! *p_n! = 0

相当于

A = k₁*p₁ + ... + k_n! *p_n!

其中 0 是全为零的 n-item 数组。由于 ℕ^n 不是 ℕ-向量 space，因此您无法使用明显的线性代数解决方案来解决这个问题；实际上，在自然数上寻找线性系统的解一般是 NP-complete by a reduction from subset sum。我无法根据您的临时问题版本调整缩减，所以也许考虑一下。它应该保持 NP-hard，至少这是我所期望的。

Answer 3

可以用动态规划求解。如果您查看动态规划问题的常见解决方案，它们遵循相同的通用结构。我们使用一个数组来存储达到每个值所需的最少排列数，并使用嵌套循环依次更新每个值。答案将以 d[0][0][0] 结尾，这是达到 [0, 0, 0].

所需的排列数

public static int count(int a, int b, int c) {
    int[][] permutations = {{9, 3, 1}, {9, 1, 3}, {1, 9, 3}, {1, 3, 9}, {3, 9, 1}, {3, 1, 9}};

    int[][][] d = new int[a + 1][b + 1][c + 1];

    // Set initial values to high value to represent no solution.
    for(int x = 0; x <= a; x++) {
        for(int y = 0; y <= b; y++) {
            for(int z = 0; z <= c; z++) {
                d[x][y][z] = Integer.MAX_VALUE / 2;
            }
        }
    }

    // Set number of permutations for initial value to 0.
    d[a][b][c] = 0;

    // Update all values.
    for(int x = a; x >= 0; x--) {
        for(int y = b; y >= 0; y--) {
            for(int z = c; z >= 0; z--) {
                for(int[] p:permutations) {
                    // Update count from [x, y, z] -> [nx, ny, nz] using permutation p.
                    int nx = x - p[0];
                    int ny = y - p[1];
                    int nz = z - p[2];
                    if(nx >= 0 && ny >= 0 && nz >= 0) {
                        d[nx][ny][nz] = Math.min(d[nx][ny][nz], d[x][y][z] + 1);
                    }
                }
            }
        }
    }

    // Return final answer.
    return d[0][0][0];
}

想不通这个算法的通用名叫什么？

Can't figure out what the generic name of this algorithm is called?

algorithm

recursion

combinations

dynamic

permutation

编辑：