最优分解问题c语言

最优分解问题是指将一个正整数n分解成若干个正整数之和，使得这些正整数的乘积最大。可以使用动态规划来解决这个问题。

以下是C语言代码实现：

#include <stdio.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int n;
    scanf("%d", &n);

    int dp[n + 1];
    dp[0] = dp[1] = 0;

    for (int i = 2; i <= n; i++) {
        dp[i] = 0;
        for (int j = 1; j < i; j++) {
            dp[i] = max(dp[i], j * (i - j));
            dp[i] = max(dp[i], j * dp[i - j]);
        }
    }

    printf("%d\n", dp[n]);

    return 0;
}

首先定义一个`max`函数，用于比较两个数的大小，返回较大的数。然后读入正整数n，并定义一个数组`dp`，其中`dp[i]`表示将正整数i分解成若干个正整数之和，使得这些正整数的乘积最大的乘积值。

接下来，我们使用动态规划的思想来计算`dp`数组。首先将`dp[0]`和`dp[1]`都赋值为0。然后从`dp[2]`开始，依次计算`dp[2]`到`dp[n]`的值。

对于每个`dp[i]`，我们可以将其分解成j和i-j两个数的和，其中j是从1到i-1的正整数。因此，我们可以分两种情况考虑：

- 将i分解成j和i-j两个数的和，并将它们相乘，得到j * (i-j)这个乘积值。然后将这个乘积值和当前的`dp[i]`比较，保留较大的值。
- 将i分解成j和若干个正整数之和，使得这些正整数的乘积最大。因此，我们可以将这些正整数的乘积值看作是`dp[i-j]`，然后将j和`dp[i-j]`相乘，得到j * dp[i-j]这个乘积值。然后将这个乘积值和当前的`dp[i]`比较，保留较大的值。

最后，`dp[n]`就是将正整数n分解成若干个正整数之和，使得这些正整数的乘积最大的乘积值。