HDU 3127 WHUgirls(完全背包)

http://acm.hdu.edu.cn/showproblem.php?

pid=3127

题意:

如今有一块X*Y的矩形布条, 然后有n种规格的x[i]*y[i]的小布条, 每种布条能够卖出val[i]的价值. 问你原始的X*Y布条最多能卖多少价值? 当中每次分割布条仅仅能水平或垂直的切, 且一刀究竟.

分析:

本题看起来比較麻烦, 可是搞懂原理后还是非常easy的. 把当前还剩余的矩形布条看成容量, 那么我们就是再这有限的容量里面要找出最大价值的布条总和来.

令dp[i][j]==x 表示当前长i和宽j的布条能分割出的最大价值为x.

这里有个结论要注意: 我们每次从大矩形中分割出一个小矩形, 总是沿着大矩形的顶角边缘分割将不会丢失最优解.

比方一个i*j的大矩形, 我们假设要从中分割出一个x*y的小矩形, 有以下4种方式(大矩形能够选择先下垂直那刀或先下水平那刀, 小矩形能旋转):

(细致体会上面这个图.)

有了上面的图, 以下我们的递推公式就出来了:

if(i>=r[k].x&& j>=r[k].y)

dp[i][j]=max(dp[i][j] , max( dp[i-r[k].x][j]+dp[r[k].x][j-r[k].y] ,dp[i-r[k].x][r[k].y]+dp[i][j-r[k].y] )+r[k].val );

if(i>=r[k].y && j>=r[k].x)

dp[i][j]=max(dp[i][j] , max( dp[r[k].y][j-r[k].x]+dp[i-r[k].y][j] ,dp[i-r[k].y][r[k].x]+dp[i][j-r[k].x] )+r[k].val );

上面两个公式好像看起来非常复杂, 事实上理解上面的图之后就非常easy了. 本质就是:

原始矩形能获得的最大价值 == max(小矩形价值 + 被水平一刀和竖直一刀分割后剩下的两个矩形能获得的最大价值和 )

也就是求分割后的3个矩形的价值和, 看看哪种方式分割剩下的矩形价值和最大.(两刀之后, 原始矩形必定变成3个新矩形)

初始化: dp为全0.

终于所求: dp[X][Y].

注意: 全然背包问题限制条件的维度j和物品编号的维度i的循环先后顺序是能够互换的. 可是此题必须先循环X和Y的维度, 然后才是物品编号的维度. 由于一般的全然背包问题的最优解对于物品的选取顺序没有要求, 能够先区不论什么物品. 可是此题对于原始矩形来说, 你在它的顶角边缘先分割那个小矩形是明显不同的,有可能你先分割1号矩形就得不到最优解, 可是你先分割3号矩形才干得到最优解(细致想想是不是).

AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000+5;

int X,Y;//原始矩形宽和高
int n;  //有多少个小布条
struct Node//每一个小布条
{
    int x,y;
    int val;
}r[10+5];

int dp[maxn][maxn];

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        //读取输入+初始化
        scanf("%d%d%d",&n,&X,&Y);
        for(int i=1;i<=n;i++)
            scanf("%d%d%d",&r[i].x,&r[i].y,&r[i].val);
        memset(dp,0,sizeof(dp));

        //递推,注意:先X和Y,然后才是矩形编号.
        //假设先循环矩形编号,就错了.
        for(int i=0;i<=X;i++)
        for(int j=0;j<=Y;j++)
        for(int k=1;k<=n;k++)
        {
            if(i>=r[k].x && j>=r[k].y)
                dp[i][j]=max( dp[i][j] , max( dp[i-r[k].x][j]+dp[r[k].x][j-r[k].y] , dp[i-r[k].x][r[k].y]+dp[i][j-r[k].y] )+r[k].val );
            if(i>=r[k].y && j>=r[k].x)
                dp[i][j]=max( dp[i][j] , max( dp[r[k].y][j-r[k].x]+dp[i-r[k].y][j] , dp[i-r[k].y][r[k].x]+dp[i][j-r[k].x] )+r[k].val );
        }

        //输出结果
        printf("%d
",dp[X][Y]);
    }
}