1279:【例9.23】橱窗布置(flower)

2023-12-19 21:43:11

【算法分析】
1. 状态定义
状态定义:dp[i][j]:将前i束花放入前j个瓶子中,美学值最大的方案的美学值。
初始状态:前0束花放入j个花瓶中,美学值为0。所以dp[0][j] = 0

2. 状态转移方程
记将第i束花放入第j个瓶子得到的美学值为a[i][j]
集合:将前i束花放入前j个瓶子
分割集合:根据将第i束花放入第几个瓶子来分割集合

如果把第i束花放入第j个瓶子,那么接下来需要把前i-1束花放入前j-1个瓶子中获得最大美学值。dp[i][j] = dp[i-1][j-1] + a[i][j]
如果把第i束花放入第j-1个瓶子,那么接下来需要把前i-1束花放入前j-2个瓶子中获得最大美学值。dp[i][j] = dp[i-1][j-2] + a[i][j-1]

如果把第i束花放入第i个瓶子,那么接下来需要把前i-1束花放入前i-1个瓶子中获得最大美学值。dp[i][j] = dp[i-1][i-1] + a[i][i]
以上多种情况取最大值。
综上,k从i循环到jdp[i][j] = max(dp[i][j], dp[i-1][k-1] + a[i][k])

3. 具体做法:
1. 瓶子编号j的循环范围
由于每束花都要放在某个花瓶中,前i束花放入前j个瓶子中,瓶子数量必须大于等于花的数量,所以j ≥ i
一共有f束花v个瓶子,在前i束花放入前j个瓶子时,还剩下f-i束花,v-j个瓶子,剩下的瓶子的数量也一定要大于等于花的数量,因此v ? j ≥ f ? i ,即j ≤ v ? f + i
所以j从i循环到v-f+i

2. 记录方案
设数组b,b[i][j]表示如果将前i束花放入前j个瓶子,第i束花所在的瓶子。
如果确定将花放入第k瓶子能获得最大美学值,可以更新dp[i][j],那么也同时更新b[i][j] = k
输出时通过递归的方法逆序输出,前i束花放入前j个瓶子,第i束花在b[i][j],那么先输出前i-1束花放在前b[i][j]-1个瓶子中的情况,再输出b[i][j]。

【参考代码】
?

#include<bits/stdc++.h>
using namespace std;
#define N 105
int f, v, a[N][N], dp[N][N];//dp[i][j]:前i个束花放在前j个花瓶中能得到的最大美学度
int b[N][N];//b[i][j]:前i个花束放入前j个瓶子,第i束花在哪个瓶子 
void show(int i, int j)//输出前i个花束放入前j个瓶子各花束的位置 
{
	if(i == 0)
		return;
	show(i-1, b[i][j]-1);
	cout << b[i][j] << ' ';
}
int main()
{
    cin >> f >> v;
    for(int i = 1; i <= f; ++i)
        for(int j = 1; j <= v; ++j)
            cin >> a[i][j];
	memset(dp, 0xc0, sizeof(dp));//初始化为负无穷
    for(int j = 0; j <= v; ++j)
    	dp[0][j] = 0;
	for(int i = 1; i <= f; ++i)
        for(int j = i; j <= v-f+i; ++j)
            for(int k = i; k <= j; ++k)
            {
        	    if(dp[i][j] < dp[i-1][k-1] + a[i][k])
        	    {
        	       	dp[i][j] = dp[i-1][k-1] + a[i][k];
        		    b[i][j] = k; 
        	    }
        	}
    cout << dp[f][v] << endl;
    show(f, v);
    return 0;
}

文章来源:https://blog.csdn.net/pheatonhb/article/details/135087897
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。