无法弄清楚这个算法的通用名称是什么？

I just did a Top Coder SRM where there was a question I had problem solving. I am trying to searching online for details of the algorithm but I can't seem to find it.

我刚做了一个Top Coder SRM,其中有一个问题我解决了问题。我试图在网上搜索算法的细节,但我似乎无法找到它。

The question went around the lines of: You have an array, for example [12, 10, 4]

问题围绕着:你有一个阵列,例如[12,10,4]

Each round, you can apply any permutation of 9,3,1 to subtract from [12,10,4]

每轮,你可以应用任何9,3,1的排列减去[12,10,4]

Return the minimum amount of permutations needed to be applied to get to 0 for all numbers in the array.

返回所需的最小排列量,以便为数组中的所有数字设置为0。

Any help?

Edit: Let me be somewhat more descriptive so that the question can be understood better.

编辑:让我更具描述性,以便更好地理解问题。

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

Edit2:

Here is the topcoder question: http://community.topcoder.com/stat?c=problem_statement&pm=13782

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

Edit3: Can anyone also explain the Overlapping Subproblem and Optimal Substructure if they believe a solution is with dynamic programming?

编辑3:任何人都可以解释重叠子问题和最佳子结构,如果他们认为解决方案是动态编程?

3 个解决方案

#1

EDIT :

after seeing the original question, here is the solution which gave correct output for every testcase provided in above question link, if u want give input {60} , u shud give as {60,0,0} .

在看到原始问题之后,这里是为上述问题链接中提供的每个测试用例提供正确输出的解决方案,如果您想要输入{60},则uud给出为{60,0,0}。

Basic idea is , u need to get all of them less than or equal to zero atlast , so if number is divisible by 3 , u can get zero by subtracting 9 or 3 and if not divisible, subtract by 1 to make it divisible by 3

基本的想法是,你需要让所有这些都小于或等于零atlast,所以如果数字可以被3整除,你可以通过减去9或3来得到零,如果不能被整除,则减去1使其可被3整除

first , sort the given triplet , then

首先,对给定的三元组进行排序

• check the largest number is divisible by 3, if so, subtract 9 and the number still can be divisible by 3

检查最大数字是否可被3整除,如果是,则减去9,数字仍然可以被3整除

• now check the next largest number , if it is divisible by 3, subtract 3 else subtract 1

现在检查下一个最大的数字,如果它可被3整除,则减去3,否则减去1

• if largest number is not divisible by 3, subtract 1 so that it may be divisible by 3

如果最大数字不能被3整除,则减去1使其可以被3整除

• now subtract next largest number by 9 and the other one by 3

现在减去下一个最大的数字9,另一个减去3

here is the implementation

这是实施

#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;
}

hope this is helpful

希望这是有帮助的

Example: input is [12,4,10]

示例:输入为[12,4,10]

sort it [12,4,10] -> [12,10,4]

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

now check if largest number is divisible by 3, here Yes

现在检查最大数字是否可被3整除,这里是

so [12-9,10,4] -> [3,10,4] now check next largest number divisible by 3, here N0

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

so [3,10-1,4-3] ->[3,9,1]

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

now increment count and pass this to function(recursive)

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

input -> [3,9,1]

输入 - > [3,9,1]

sort [3,9,1] -> [9,3,1]

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

now check if largest number is divisible by 3, here Yes

现在检查最大数字是否可被3整除,这里是

so [9-9,3,1] -> [0,3,1]

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

now check next largest number divisible by 3, here Yes

现在检查下一个可被3整除的最大数字,这里是

so [0,3-3,1-1] -> [0,0,0]

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

now increment the count and pass the array

现在递增计数并传递数组

as largest element is 0 , we will print count and that is 2

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

#2

Let the number of elements be n, let p₁ to p_n! be the permutations of the array you want to subtract, and let A be your original array. Then you want the natural numbers solutions of the linear system

让元素的数量为n,让p1到pn!是要减去的数组的排列,让A成为原始数组。那么你想要线性系统的自然数解

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

A - k1 * p1 - ... - kn!* pn! = 0

which is equivalent to

这相当于

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

A = k1 * p1 + ... + kn!* pn!

where 0 is the n-item array with all zeroes. You can't figure that out using the obvious linear algebra solution since ℕ^n is not an ℕ-vector space; actually, finding solutions to linear systems over natural numbers in general is NP-complete by a reduction from subset sum. I couldn't adapt the reduction to your version of the problem ad hoc, so maybe think about that for a bit. It should remain NP-hard, at least that's what I would expect.

其中0是全零的n项数组。你无法用明显的线性代数解来解决这个问题,因为ℕ^ n不是ℕ向量空间;实际上,一般来说,通过自然数来找到线性系统的解是通过从子集和减少来完成NP。我无法将减少量调整到您的特定问题版本,所以也许可以考虑一下。它应该保持NP难度,至少这是我所期望的。

#3

It can be solved using dynamic programming. If you look at common solutions to dynamic programming problems, they follow the same general structure. We use an array to store the minimum number of permutations needed to reach each value, and update each value in turn using nested loops. The answer will end up in d[0][0][0] which is the number of permutations required to get to [0, 0, 0].

它可以使用动态编程来解决。如果您看一下动态编程问题的常见解决方案,它们遵循相同的一般结构。我们使用数组来存储达到每个值所需的最小排列数,并使用嵌套循环依次更新每个值。答案将以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];
}