使用动态规划解花店问题两种思考方法分析

fuliang

浏览: 1653776 次
性别:
来自: 北京

最近访客更多访客>>

依然任逍遥

stephenworld

lli

samwalt

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

Algorithm

J#F#

问题描述：

LITTLE SHOP OF FLOWERS
Description
You want to arrange the window of your flower shop in a most pleasant way. You have F bunches of flowers, each being of a different kind, and at least as many vases ordered in a row. The vases are glued onto the shelf and are numbered consecutively 1 through V, where V is the number of vases, from left to right so that the vase 1 is the leftmost, and the vase V is the rightmost vase. The bunches are moveable and are uniquely identified by integers between 1 and F. These id-numbers have a significance: They determine the required order of appearance of the flower bunches in the row of vases so that the bunch i must be in a vase to the left of the vase containing bunch j whenever i < j. Suppose, for example, you have bunch of azaleas (id-number=1), a bunch of begonias (id-number=2) and a bunch of carnations (id-number=3). Now, all the bunches must be put into the vases keeping their id-numbers in order. The bunch of azaleas must be in a vase to the left of begonias, and the bunch of begonias must be in a vase to the left of carnations. If there are more vases than bunches of flowers then the excess will be left empty. A vase can hold only one bunch of flowers.

Each vase has a distinct characteristic (just like flowers do). Hence, putting a bunch of flowers in a vase results in a certain aesthetic value, expressed by an integer. The aesthetic values are presented in a table as shown below. Leaving a vase empty has an aesthetic value of 0.

	V A S E S
1	2	3	4	5
Bunches	1 (azaleas)	7	23	-5	-24	16
2 (begonias)	5	21	-4	10	23
3 (carnations)	-21	5	-4	-20	20

According to the ta ble, azaleas, for example, would look great in vase 2, but they would look awful in vase 4.

To achieve the most pleasant effect you have to maximize the sum of aesthetic values for the arrangement while keeping the required ordering of the flowers. If more than one arrangement has the maximal sum value, any one of them will be acceptable. You have to produce exactly one arrangement.

Input

The first line contains two numbers: F, V.
The following F lines: Each of these lines contains V integers, so that Aij is given as the jth number on the (i+1)st line of the input file.

1 <= F <= 100 where F is the number of the bunches of flowers. The bunches are numbered 1 through F.

F <= V <= 100 where V is the number of vases.

-50 <= Aij <= 50 where Aij is the aesthetic value obtained by putting the flower bunch i into the vase j.

Output
The first line will contain the sum of aesthetic values for your arrangement.

Sample Input

3 5
7 23 -5 -24 16
5 21 -4 10 23
-21 5 -4 -20 20

Sample Output

分析：
这个问题简单描述一下，就是F束花，插在V个花瓶中，花和花瓶都有编号，分别为 1..F和1..V,花插在花瓶中，
需要按照编号的顺序插，例如1号不能插在2号的后边，每个花瓶只能插一束花。插在不同的瓶子上，都有不同的美观的值。(F<=V)
问题要求把F朵花，插在V个花瓶中有最大的美观值。

第一种方法的建立递推关系：
建立递推关系：
v[i[j]为第i朵花插到第j个花瓶上的美观值
most_b[i][j]表示，最后一朵花i，插在了第j个花瓶上的最大美观值。
most_b[i][j] = max{most_b[i-1][k]} + v[i][j] k = i-1...j-1
这个递推是的含义是：把i朵花插到j个花瓶上，并且第i朵插到第j个花瓶上了，他的值为把前i-1多花插到了
前k个花瓶上，并且第i-1朵插到第k个花瓶上了(由于顺序的限制，k的值只能为i-1到j-1)的最大值再加上把
第i朵插到第j个花瓶上的美观值。
得到这个递推关系就很容易写程序了：

cpp 代码

#include<iostream></iostream>
using namespace std;
int main(){
int i,j,k;
int most_b[100][100];//most_b[i][j]表示，最后一朵花i，插在了j个花瓶上的最大美观值
int v[100][100];//v[i[j]为第i朵花插到第j个花瓶上的美观值
const int MIN = -10000;
int F,V;//F多花，V个花瓶
int max = MIN;//最终的最大美观值
cin >> F >> V;
for(i = 0; i < F; i++)
for(j = 0; j < V; j++){
cin >> v[i][j];
most_b[i][j] = MIN;
}
for(i = 0; i < V; i++)//初始化，把一朵花插到V个花瓶的最大美观值，为v[0][i]
most_b[0][i] = v[0][i];
for(i = 1; i < F; i++)
for(j = i; j < V; j++)
for(k = i-1; k < j; k++)//递推求最大美观值
if(most_b[i-1][k] + v[i][j] > most_b[i][j])
most_b[i][j] = most_b[i-1][k] + v[i][j];
for(i = F-1; i < V; i++)//最后一朵花插到了F-1到V那么多种可能的最大值即为所求的最大美观值
if(max < most_b[F-1][i])
max = most_b[F-1][i];
cout << max << endl;
return 0;
}

第二种方法建立递推关系：
v[i[j]为第i朵花插到第j个花瓶上的美观值
我们换一个角度来考虑：
现在用most_b[i][j]表示把i朵花插到j个花瓶的最大美观值，我们想以此建立递推关系：
most_b[i][j] = max{most_b[i][j-1],most_b[i-1][j-1] + v[i][j]}
这个递推关系的含义是：
把i朵花插到j个花瓶的最大美观值=
max{把i朵花插到j-1个花瓶的最大美观值，把i-1朵花插到j-1个花瓶的最大美观值+把第i朵花插到第j个花瓶的美观值}
得到这个递推关系写出的代码要比上面的效率高：
为了方便，most_b的0行和0列没用，都从1开始

cpp 代码

#include<iostream></iostream>
using namespace std;
int main(){
int i,j;
int most_b[101][101];
int v[101][101];
const int MIN = -50001;
int F,V;
int max = MIN;
cin >> F >> V;
for(i = 1; i <= F; i++)
for(j = 1; j <= V; j++){
cin >> v[i][j];
most_b[i][j] = MIN;
}
//通过most_b[0][i]辅助作用可以减少不少代码，
//如果不用most_b[0][i]，你需要初始化most_b第一行的值为v第一行的值
//第一列维most_b[i][1] = max{v[i..i][1]}
//通过下面初始化，把上面两个初始化操作合并到了递推求解那个循环中了
for(i = 0; i <= V; i++)
most_b[0][i] = 0;
//从底向上递推求解：
for(i = 1; i <= F; i++)
for(j = i; j <= i + V-F; j++)
if(most_b[i][j-1] > most_b[i-1][j-1] + v[i][j])
most_b[i][j] = most_b[i][j-1];
else
most_b[i][j] = most_b[i-1][j-1] + v[i][j];
cout << most_b[F][V] << endl;
return 0;
}

分享到：

动态规划小结 | 用动态规划解--滑雪题算法分析

2007-12-26 21:38
浏览 2550
评论(0)
查看更多

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论