資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學最大化C++中長度為p、q和r的線段數量
問題陳述
給定一根長度為L的杆，任務是將杆切割成若干段，使得長度為p、q和r的線段總數最大化。線段長度只能為p、q和r。
如果l = 15，p = 2，q = 3，r = 5，則可以得到如下7段：
{2, 2, 2, 2, 2, 2, 3}演算法
我們可以使用動態規劃來解決這個問題。
1. Initialize dp[] array to 0 2. Iterate till the length of the rod. For every i, a cut of p, q and r if possible is done. 3. Initialize ans[i+p] = max( ans[i+p], 1 + ans[i]), ans[i+q] = max(ans[i+q], 1 + ans[i]) and ans[i+r] = max(ans[i+r], 1 + ans[i]) for all the possible cuts. 4. ans[i] will be 0 if a cut at i-th index is not possible. ans[l] will give the maximum number of cuts possible
示例
#include <bits/stdc++.h>
using namespace std;
int getMaximumSegments(int l, int p, int q, int r){
int dp[l + 1];
memset(dp, -1, sizeof(dp));
dp[0] = 0;
for (int i = 0; i <= l; ++i) {
if (dp[i] == -1) {
continue;
}
if (i + p <= l) {
dp[i + p] = max(dp[i + p], dp[i] + 1);
}
if (i + q <= l) {
dp[i + q] = max(dp[i + q], dp[i] + 1);
}
if (i + r <= l) {
dp[i + r] = max(dp[i + r], dp[i] + 1);
}
}
return dp[l];
}
int main(){
int l = 15, p = 2, q = 3, r = 5;
cout << "Number of segments = " << getMaximumSegments(l, p, q, r) << endl;
return 0;
}輸出
編譯並執行上述程式後，會生成以下輸出：
Number of segments = 7
更新於：2019年12月24日
136 次瀏覽
廣告