找路线和最大面积问题

题目描述】小明有N（4≤N≤60）个玻璃球，他想将N个玻璃球拆分成若干份（份数≥2，且每份中的数量互不相等），从而使拆分后的每份玻璃球数量的乘积最大。请你编写程序帮助小明计算出最大乘积是多少

找路线：

#include <iostream>
using namespace std;
int main()
{
    int n, m;
    cin >> n >> m;
    n = m - n + 1;
    int a = 1, b = 1, c = a + b;
    for (int i = 2; i <= n; i++)
    {
        c = a + b;
        a = b;
        b = c;
    }
    cout << a << endl;
    return 0;
}

求乘积

#include<iostream>
using namespace std;
int n, a[30];
int main()
{
    cin >> n;
    int x = 2;
    while (x <= n)
    {
        a[x] = x;
        n -= x;
        x++;
    }
    if (n == x - 1) a[x - 1]++;
    for (int i = x - 1; n >= 1 && i >= 2; i--)
    {
        a[i]++;
        n--;
    }
    int ans = 1;
    for (int i = 2; i < x; i++) ans *= a[i];
    cout << ans << endl;
    return 0;
}

找路线

#include<stdio.h>

int main(){

    int n, m;
    scanf("%d %d", &n, &m);

    int a[23];

    a[0] = 0;
    a[1] = 1;
    a[2] = 2;

    for( int i = 3; i <=22; i++){
        a[i] = a[i-1] + a[i-2];
    }

    printf("%d", a[m-n]);

    return 0;
}

求乘积

#include<stdio.h>

int main(){

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

    int a[61];

    a[2] = 2;
    a[3] = 3;
    a[4] = 4;
    
    for( int i = 5; i <= n; i++ ) {
        a[i] = 0;
        for( int j = 2; j <= i/2; j++) {
            int tmp = j * a[i-j];
            a[i] = a[i] > tmp ? a[i]: tmp;
        }
    }

    printf("%d", a[n]);

    return 0;
}

又是一个穷举算法的问题

我觉得可以使用贪心算法来解决这个问题。贪心算法的思路是，每次都将玻璃球拆分成两份，使得两份的乘积最大。

#include <iostream>

using namespace std;

int main()
{
int n;
cin >> n;
int ans = 1;
while (n > 1)
{
ans *= (n / 2);
n -= (n / 2);
}
cout << ans << endl;
return 0;
} 

假设输入的数为n，那么循环的条件是n>1。每次循环中，计算n/2的结果并将其乘到答案ans中。然后将n减去n/2的结果。最后，输出ans的值即可。

这样，每次循环后，n的值都会减少一半，直到n<=1为止。这样，就可以保证每次拆分的两份中的数量乘积最大。
此代码的时间复杂度为O(log n)，空间复杂度为O(1)。
望采纳！谢谢！

#include <stdio.h>

int main()
{
    int n;
    scanf("%d", &n); // 输入玻璃球的数量

    int a = (n-1) / 2; // 第一份的数量
    int b = (n+1) / 2; // 第二份的数量

    // 计算并输出最大乘积
    long long result = (long long)a * b;
    printf("%lld\n", result);

    return 0;
}

动态规划之最大面积(C++实现)
借鉴下
https://blog.csdn.net/weixin_42662358/article/details/100915168