将整数按数组元素分解

Question

整数分解问题
任意给定一个大于1000的正整数，将其分解成下列若干个整数（可重复）的和:57,71,87,97,99,101,103,113,114, 115, 128,129,131,137,147,156, 163, 186.
请编写一个函数，输入参数为一个大于1000且小于60000的正整数，输出参数为分解方案。
（例如：输入参数为1530，输出参数为1530=87+993+128+1372+186*4）

Answer 1

对于这个问题，一种可能的解决方案是使用动态规划。以下是一个简化版的C代码实现，由于C语言不支持动态数组，所以这里仅给出了核心算法部分：

#include <stdio.h>

#define MAX 60000
#define NUM 18

int comp[MAX+1] = {0}; // 组成的数的个数
int path[MAX+1] = {0}; // 最后加的数
int numList[NUM] = {57,71,87,97,99,101,103,113,114,115,128,129,131,137,147,156,163,186}; // 可用的数

void solve(int target) {
    int i, j;
    for (i = 1; i <= target; i++) {
        for (j = 0; j < NUM; j++) {
            if (numList[j] <= i && comp[i - numList[j]] + 1 > comp[i]) {
                comp[i] = comp[i - numList[j]] + 1;
                path[i] = i - numList[j];
            }
        }
    }

    // 打印结果
    printf("%d=", target);
    while (path[target] != 0) {
        printf("%d+", target - path[target]);
        target = path[target];
    }
    printf("%d\n", target);
}

int main() {
    int target = 1530;
    solve(target);
    return 0;
}

这段代码首先初始化了一个长度为target+1的数组comp，用于存储组成每个数的最小个数，以及一个路径数组path，用于回溯每个数是由哪两个数相加得来的。然后，通过双重循环，寻找可以组成每个数的最小个数，以及路径。最后，通过回溯路径数组，打印出组成target的数。

注意：这个解决方案可能并不完全满足题目要求，因为它是找的最小个数的组合，而题目可能存在多个解。你可能需要根据实际需要对其进行调整。