题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3127
题目大意：将一块长x宽y的矩形布料，剪成小的矩形（每个给定的小矩形都对应一个价值），使得所有小矩形产生的价值最大。
Sample Input
1
2 4 4
2 2 2
3 3 9
Sample Output
9
分析：
这题可以可以看做完全背包问题来接。因为：1、每种矩形布可以剪任意多个；2、题目给出的矩形布可以看做背包容量；3、每个矩形布都有一个价值
关键在于找到状态转移方程：设dp[i][j]为长为i宽为j的矩形布的最大价值，下面的图一可以看做待剪的布，图二为小布的尺寸
对于这个问题可以两种如下剪布方案：
易知剪布后的价值为每个图形中三块之和。
对于方法一：
dp[i][j] = max(dp[i][j], dp[i-p[k].x][j]+dp[p[k].x][j-p[k].y]+p[k].value, dp[i][j-p[k].y]+dp[i-p[k].x][p[k].y]+p[k].value);
对于方法二：
dp[i][j] = max(dp[i][j], dp[i-p[k].y][j]+dp[p[k].y][j-p[k].x]+p[k].value, dp[i][j-p[k].x]+dp[i-p[k].y][p[k].x]+p[k].value);
代码如下：
# include<iostream>
# include<cstdio>
# include<cstring>
using namespace std;
struct node{
int x,y,value;
}p[];
int dp[][]; int max(int a,int b,int c){
int temp = a>b?a:b;
return temp>c?temp:c;
} int main(){
int T,n,x,y;
int i,j,k;
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&x,&y);
for(i=;i<n;i++)
scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].value);
memset(dp,,sizeof(dp));
for(i=;i<=x;i++){
for(j=;j<=y;j++){
for(k=;k<n;k++){
if(i>=p[k].x &&j>=p[k].y)
dp[i][j] = max(dp[i][j], dp[i-p[k].x][j]+dp[p[k].x][j-p[k].y]+p[k].value,
dp[i][j-p[k].y]+dp[i-p[k].x][p[k].y]+p[k].value);
if(i>=p[k].y &&j>=p[k].x)
dp[i][j] = max(dp[i][j], dp[i-p[k].y][j]+dp[p[k].y][j-p[k].x]+p[k].value,
dp[i][j-p[k].x]+dp[i-p[k].y][p[k].x]+p[k].value);
}
}
}
printf("%d\n",dp[x][y]);
}
return ;
}