AHU 算法分析 实验四 动态规划

实验四：动态规划

实验目的

• 理解动态规划的基本思想，理解动态规划算法的两个基本要素最 优子结构性质和子问题的重叠性质。

• 熟练掌握典型的动态规划问题。

• 掌握动态规划思想分析问题的一般方法，对较简单的问题能正确 分析，设计出动态规划算法，并能快速编程实现。

钢条切割问题

有一段长度为n的钢条，钢条可以被分割成不同的长度的小钢 条出售，不同的小钢条对应不同的售价。详见下表:

钢条切割问题是这样的： 给定⼀段长度为n的钢条和⼀个价格表 pi(i=1,2,…n)， 求切割钢条⽅案， 使得销售收益最⼤。 注意， 如果长度为n英⼨的钢条的价格pn⾜够⼤， 最优解可能就是完全不需 要切割。

输入：钢条的长度n，不同长度钢条的价值Pi，{i=1，…，n}

输入：1、最大收益，2、切割方案。

问题分析

我们选用一个状态方程去描述问题，设f(i,j)为状态方程，含义是在0~i种可被切割长度，j为当前钢条长度，举例f(3,5)意思就是在当前长度为5的时候，钢条可被切成0，1，2，3，这几种长度。

当我们不选择第i种切割方式时，那么还剩i-1种切割方式，所以有状态转移方程
$$f(i,j)=f(i-1,j)$$
当我们选择第i种切割方式的时候，如果此时$i>j$, 那么应该放弃这种方案，即状态转移方程为
$$f(i,j)=f(i-1,j)$$
如果此时$i<=j$, 因为这种方式可能被选择多次，所以我们选择k次来表示，以不失一般性，那么状态转移方程为
$$f(i,j)=max(\sum _{k=0}^{+\infty }f(i-1,j-k\ast i)+k\ast a[i])$$
然后将选择第i种方案合并，即状态转移方程为
$$f(i,j)=max(f(i-1,j),\sum _{k=0}^{+\infty }f(i-1,j-k\ast i)+k\ast a[i])$$
这里我们进行一个数学方程的变换
$$f(i,j-i)=max(\sum _{k=0}^{+\infty }f(i-1,j-(k+1)\ast i)+k\ast a[i])$$
可以将两个式子联立
$$f(i,j)=max(f(i-1,j),f(i,j-i)+a[i])$$
分析完毕

源代码

#include 
using namespace std;

int a[1000];
int dp[1000][1000];
int x[1000];

int fun(int len) {
	for (int i = 1; i <=len; i++) {
		for (int j = 0; j <=len; j++) {
            dp[i][j]=dp[i-1][j];
            if(j>=i)
			dp[i][j] = max(dp[i-1][j], dp[i][j - i] + a[i]);
		}
	}
	return dp[len][len];
}

void traceback(int j, int y)
{
	while (j) {
		while (y < j) {
			j--;
		}
		if (dp[j][y] == (dp[j][y - j] + a[j]))                                  
		{
			x[j]++;
			y = y - j;
			++j;
		}
		j--;
	}
}
int main(){
	int len = 0;
	int sum = 0;
	bool flag=1;
	cin >> len;
	for (int i = 1; i <= len; i++) {
		scanf("%d", &a[i]);
	}
	cout << fun(len)<