資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究將數字分成 3 部分以找到最大和
給定一個數字。我們的任務是將數字透過 n/2、n/3 和 n/4 三次分割，並找到透過將數字分成三個部分可以獲得的最大和。
例如，50 可以分成 {25, 16, 12}，現在將集合 {25, 16, 12} 中的每個部分再次分成三個部分，依此類推。在完成最多 3 次分割後，我們將計算總和以找到其中的最大值。
此程式可以用遞迴方式解決，但在遞迴方法中，我們需要多次找到相同的結果，因此，如果我們使用動態規劃方法並將先前計算的資料儲存在表中，則可以減少時間。
輸入和輸出
Input: Let the given number is 12. Output: The answer is 13. At first divide the 12 as (12/2 + 12/3 + 12/4) = 6 + 4 + 3 = 13. now divide 6 into three parts (6/2 + 6/3 + 6/4) = 3 + 2 + 1 = 6. If we divide the 4 and 3, we can get maximum 4 from them. From all values the maximum is 13.
演算法
maxBreakSum(n)
輸入：給定的數字。
輸出：分割後的最大和。
Begin define sums array of size n+1 sums[0] := 0, sums[1] := 1 for i in range 2 to n, do sum[i] := maximum of i and (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; //for number 0 and 1, the maximum sum is 0 and 1 respectively
for (int i=2; i<=n; i++) //for number 2 to n find the sum list
sumArr[i] = max(sumArr[i/2] + sumArr[i/3] + sumArr[i/4], i); //divide number by 2, 3, 4
return sumArr[n];
}
int main() {
int n;
cout << "Enter a number: "; cin >> n;
cout << "Maximum sum after breaking: " << maxBreakSum(n);
}輸出
Enter a number: 12 Maximum sum after breaking: 13
更新於： 2020年6月17日
455 次檢視
廣告