第三次作業【動態規劃】

<1>算法實現題 3-1 獨立任務最優解問題

▲問題重述

用兩臺處理機A 和 B處理n 個作業。設第個作業交給機器A處理時需要時間ai，若由機器 B 來處理，則需要時間 b。由于各作業的特點和機器的性能關系，可能對于某些，有azb，而對于某些jjfi)，有ab。既不能將一個作業分開由兩臺機器處理也沒有一臺機器能同時處理2個作業。設計一個動態規劃算法，使得這兩臺機器處理完這n
個作業的時間最短(從任何一臺機器開工到最后一臺機器停工的總時間)。研究一個實例:(a1,a2,a3,a4,as,a6)=(2,5,7,10,5,2)，(b, b2,b, b4, bs, b6)=(3,8,4,11,3,4)。

算法設計:對于給定的兩臺處理機A 和 B 處理個作業，找出一個最優調度方案，使2
臺機器處理完這n個作業的時間最短。

數據輸入:由文件 inputtxt 提供輸入數據。文件的第1行是1個正整數n，表示要處理
n個作業。在接下來的2行中，每行有n個正整數，分別表示處理機A和B 處理第i個作業需要的處理時間。

案例：

input.txt
6
2 5 7 10 5 2
3 8 4 11 3 4output.txt
15

▲解題思路

狀態轉移方程：dp[i][j]=min(dp[i-1][j]+b[i],dp[i-1][j-a[i]]);

dp[i][j]代表做完前i個任務，A機器花幾分鐘情況下，B機器所花的時間，也就是說dp[i][j]就是表示B機器所花時間。

dp[i][j] = dp[i-1][j]+b[i]代表第i個任務交給B來做，所以做完前i個任務的時候,A機器和前i - 1的任務一樣，還是花了j分鐘，而B機器則花dp[i-1][j]+b[i]分鐘；

dp[i][j] = dp[i-1][j-a[i]]代表第i個任務交給A來做，現在的A機器花費時間是j，所以在前i - 1個任務完成的時候，A機器是花了j-a[i]分鐘的，所以現在B機器還是花了dp[i-1][j-a[i]]分鐘；

一直到dp[n][i]:代表所有的任務都做完了，B機器所花費的時間，那么最遲的時間就是B的時間和A的時間求最大值；

最后這個循環for(int i=0; i<=sum; i++)ans=min(ans,max(dp[n][i],i));//max(dp[n][i],i) 表示完成前n個作業A機器花i分鐘 B機器花dp[n][i]分鐘情況下，最遲完工時間

▲代碼

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e6 + 100;
const double eps = 1e-6;
int Data[MAXN];
int a[MAXN], b[MAXN];
int dp[500][1000];
int main(){freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);int n;int maxn = 0;cin >> n;for(int i=1;i<=n;i++){cin >> a[i];maxn += a[i];}for(int i=1;i<=n;i++) cin >> b[i];for(int i=1;i<=n;i++){for(int j=0;j<=maxn;j++){if(j < a[i]){   dp[i][j] = dp[i - 1][j] + b[i];}else{dp[i][j] = min(dp[i - 1][j - a[i]], dp[i - 1][j] + b[i]);}}}int ans = INF;for(int i=0;i<=maxn;i++){if(i < dp[n][i]){ans = min(ans, dp[n][i]);}else{ans = min(ans, i);}}cout << ans;return 0;
}

▲驗證

<2>算法實現題 3-4 數字三角形問題

▲問題重述

定一個由n行數字組成的數字三角形，試設計一個算法，計算出從三角形的頂至底的一條路徑，使該路徑經過的數字總和最大。數據輸入： 由文件input.txt提供輸入數據。文件的第1行是數字三角形的行數n，(1≤n≤100)。接下來n行是數字三角形各行中的數字。所有數字在0~99之間。結果輸出：將計算結果輸出到文件output.txt。文件第1行中的數是計算出的最大值。示例：如右圖所示，從 7→3→8→7→5的路徑產生了最大權值30。

▲解題思路

這道題可以用動態規劃來做，重點是表示狀態和寫狀態轉移方程設 v[i,j] 為點 (i,j) 上的值，f[i,j] 表示由 (1,1) 到 (i,j) 的路徑最大總和，則 f[i,j]=Max{f[i-1,j-1],f[i-1,j]}+v[i,j]。

此處注意“左上角點”對應的是點 (i-1,j-1)，右上角對應的是點 (i-1,j)。邊界條件更加容易想到，是 f[i][0]=f[0][j]=0 (0<=i,j<=n)。最后還需注意一點。如果淺學過DP可能下意識輸出 f[n][n]，但根據題目中“到底部任意處結束”可以看出，總和最大的路徑可能終結于 (n,1) 到 (n,n) 的任意一點，最后還需要再從中尋找最大的 f[n,j]。

整理思路，首先二重循環輸入三角形存儲于 a[][] 中，再設一 f[][] 用二重循環求解后，從 f[n][1] 至 f[n][n] 中找到最大值輸出。

▲代碼

#include<bits/stdc++.h>
using namespace std;
int a[1010][1010],f[1010][1010];
int main(){int n,s=0;cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)cin>>a[i][j];for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];for(int j=1;j<=n;j++) s=max(s,f[n][j]);cout<<s;return 0;
} 

▲驗證：

洛谷P1216 [USACO1.5] [IOI1994]數字三角形 Number Triangles（https://www.luogu.com.cn/problem/P1216）

<3>算法實現題 3-8 最小m段和問題

▲問題重述

給定n個整數組成的序列，現在要求將序列分割成m段，每段子序列中的數在原數列中連續排列。如何分割才能使m段子序列的和的最大值達到最小？

數據讀入/讀出：

第一行中有2個正整數n和m。正整數n是序列的長度，正整數m是分割的段數。接下來的一行中有n個整數。

▲解題思路

使用dp[i][j]放置將前i個數分成j段的最大最小值。
所以dp[i][1]就是前i個數的和，dp[i][1] = dp[i-1][1] + a[i];
當j>1的時候，假設前k個數為j-1段，從k~i為第j段,所以前j-1段的最大最小值為:dp[k][j-1] (前k個數分為j-1段).
最后一段為：dp[i][1]-dp[k][1] (前i個數的和減去前k個數的和)
這兩個值中選取一個最大值，當所有情況討論結束后，選出結果中最小的作為dp[i][j]的值。

因此，狀態轉移方程為

dp[i][j] = min{ max{ dp[k][j-1], dp[i][1]-dp[k][1] } } (0<k<i)

▲代碼

#include <iostream>
using namespace std;int dp[500][500];
int t[500];
void solve(int n, int m)
{int i, j, k, temp, maxt;for (i = 1; i <= n; i++)dp[i][1] = dp[i - 1][1] + t[i];for (j = 2; j <= m; j++){for (i = j; i <= n; i++){for (k = 1, temp = INT_MAX; k < i; k++){maxt = max(dp[i][1] - dp[k][1], dp[k][j - 1]);if (temp > maxt)temp = maxt;}dp[i][j] = temp;}}
}int main()
{int n, m;cin >> n >> m;if ((n < m) || (n == 0)){cout << 0 << endl;return 0;}for (int i = 1; i <= n; i++)cin >> t[i];solve(n, m);cout << dp[n][m] << endl;
}

▲驗證

<4>算法實現題 3-25 m處理器問題

▲問題重述

▲解題思路

▲代碼

#include <cmath>
#include <iostream>
using namespace std;double g[500][500];
double t[500];
int n, m;double f(int a, int b)
{double ret = 0;for (int i = a; i <= b; i++){ret += (t[i] * t[i]);}return sqrt(ret);
}double solve()
{int i, j, k;double tmp, maxt;tmp = f(n - 1, n - 1);for (i = n - 1; i >= 0; i--){if (f(i, i) > tmp)tmp = f(i, i);g[i][1] = f(i, n - 1);if (n - i <= m)g[i][n - i] = tmp;}for (i = n - 1; i >= 0; i--){for (k = 2; k <= m; k++){for (j = i, tmp = INT_MAX; j <= n - k; j++){maxt = max(f(i, j), g[j + 1][k - 1]);if (tmp > maxt)tmp = maxt;}g[i][k] = tmp;}for (k = n - i + 1; k <= m; k++)g[i][k] = g[i][n - i];}return g[0][m];
}int main()
{cin >> n >> m;for (int i = 0; i < n; i++){cin >> t[i];}cout << solve() << endl;
}

▲驗證