动态规划--石子合并

假期 2020.01.15

---

题目描述

沿着一条直线，摆放N堆石子，每一堆的石子的数目不一，规定每次只能移动相邻的两堆石子合并，合并花费为新合成的一堆石子的数量，求将这N堆石子合并成一堆的总花费的最大值以及最小值。

---

问题分析

这个问题考虑后，可以有两种方法解决，一种是采用贪心算法解决问题，一种是采取动态规划的问题解决问题，但是经过验证可知，贪心算法并不能准确计算出最大值与最小值，因此，此处采用动态规划的思路解决该问题。具体相关问题可参考本博主博文——动态规划–最优三角部分

---

思路解答

1. 借助前面问题动态规划–最优三角部分近似的解题思路，我们很容易想到，若已知直线堆列{P1，P2,P3…,Pk,P(k+1),…,P(n-1),Pn}从堆位置k处分开，可以得到最优解，那么计算合并的花费即是子问题1{P1，P2,P3…,Pk}，与子问题2{P(k+1),…,P(n-1),Pn}的问题。
2. 假设已知全部堆列合并的最优花费是c，那么子问题1{P1，P2,P3…,Pk}花费为a,子问题2{P(k+1),…,P(n-1),Pn}花费为b,{P1，P2,P3…,Pk,P(k+1),…,P(n-1),Pn}的石子数量是m,那么最优花费计算公式是：c = a + b + m
3. 那么递归式就是

最小值递归式：

Min_Weight[ i ][ j ] = min( Min_weight[i][j],Min_weight[i][k] + Min_weight[k + 1][j] + m)
其中
Min_weight[i][j]表示堆i到堆j的花费；
Min_weight[i][k]表示堆i到堆k的花费；
Min_weight[k + 1][j]表示堆k + 1到堆j的花费；
m表示堆i到堆j的石子数量之和；

同理最大值递归式：

Max_weight[i][j] = min( Max_weight[i][j],Max_weight[i][k] + Max_weight[k + 1][j] + m)
其中
Max_weight[i][j]表示堆i到堆j的花费；
Max_weight[i][k]表示堆i到堆k的花费；
Max_weight[k + 1][j]表示堆k + 1到堆j的花费；
m表示堆i到堆j的石子数量之和；

其中m的计算方法可由一下程序中的sum[ i ]数组导出：
若w( i , j ) 表示从堆 i 到堆 j 的石子数量之和，那么w( i , j )等于sum[ j ] - sum[ i - 1]；

---

代码解析

#include<iostream>
#include<algorithm>
using namespace std;
const int INF = 0x0fffffff;//最大值
const int Scale = 300;//数据规模
int Min_weight[Scale][Scale], Max_weight[Scale][Scale];//最大花费，最小花费
int sum[Scale],Position[Scale];//，Scale前所有堆值，位置值
void Search_Stone(int Position[], int num)
{
	for (int i = 1; i <= num; i++){//初始化
		Min_weight[i][i] = 0;
		Max_weight[i][i] = 0;
	}
	sum[0] = 0;//初始化
	for (int i = 1; i <= num; i++)//计算前堆i的累计石子数量
		sum[i] = sum[i - 1] + Position[i];
	for (int v = 2; v <= num; v++)//至少为两堆石子参加计算
	{
		for (int i = 1; i <= num - v + 1; i++)
		{
			int j = i + v - 1;//计算暂时终端点
			Min_weight[i][j] = INF;//初始化为最大值
			Max_weight[i][j] = -1;//初始化为最小值
			int temp = sum[j] - sum[i - 1];//记录i...j之间的石子数之和
			for (int k = i; k < j; k++){
				Min_weight[i][j] = min( Min_weight[i][j],Min_weight[i][k] + Min_weight[k + 1][j] + temp );//选出最小值
				Max_weight[i][j] = max( Max_weight[i][j],Max_weight[i][k] + Max_weight[k + 1][j] + temp );//选出最大值
			}
		}
	}
}
int main()
{
	int num;
	cout << "Please input the number of the stones: ";
	cin >> num;
	cout << "Please input the number of stones in each pile in turn: ";
	for (int i = 1; i <= num; i++)
		cin >> Position[i];
	Search_Stone(Position, num);
	cout << "最大花费是：" << Max_weight[1][num] << endl;
	cout << "最小花费是: " << Min_weight[1][num] << endl;
	return 0;
}

---

运行结果