将数字分成 3 部分以求出最大和

给定一个数字。我们的任务是将数字分成 n/2、n/3 和 n/4 三次，然后找出将数字分成三部分后可以得出的最大和。

例如，50 可以分成 {25, 16, 12}，现在将集合 {25, 16, 12} 中的每一个再次分成三部分，依此类推。完成最多 3 次除法后，我们将计算总和以找到其中的最大值。

此程序可以以递归方式解决，但在递归方法中，我们需要多次找到相同的结果，因此如果我们使用动态规划方法并将先前计算的数据存储在表中，那么它将减少时间。

输入和输出

输入:
假设给定的数字是 12。
输出:
答案是 13。
首先将 12 除以 (12/2 + 12/3 + 12/4) = 6 + 4 + 3 = 13。
现在将 6 分成三部分 (6/2 + 6/3 + 6/4) = 3 + 2 + 1 = 6。
如果我们将 4 和 3 相除，我们可以从中得到最大值 4。从所有值中，最大值为 13。

算法

maxBreakSum(n)

输入:给定的数字。

输出:拆分后的最大和。

开始
   定义大小为 n+1 的 sums 数组
   sums[0] := 0, sums[1] := 1

   对于范围从 2 到 n 的 i，执行
      sum[i] := i 和 (sums[i/2] + sums[i/3] + sums[i/d]) 的最大值
   done
   return sums[n]
End

示例

#include<iostream>
#define MAX 1000000
using namespace std;

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

int maxBreakSum(int n) {
   int sumArr[n+1];
   sumArr[0] = 0, sumArr[1] = 1;    //对于数字 0 和 1，最大和分别为 0 和 1

   for (int i=2; i<=n; i++)    //对数字 2 到 n 求和列表
      sumArr[i] = max(sumArr[i/2] + sumArr[i/3] + sumArr[i/4], i);    //将数字除以 2、3、4
   return sumArr[n];
}

int main() {
   int n;
   cout << "输入一个数字:"; cin >> n;
   cout << "拆分后的最大和:" << maxBreakSum(n);
}

输出

输入一个数字:12
拆分后的最大和:13

相关文章

• 使用两次遍历收集网格中的最大点
• 计算建造建筑物的可能方式
• 将数字分成 3 部分以求出最大和