HDU OJ 3127 WHUgirls【DP之背包】
原题连接：http://acm.hdu.edu.cn/showproblem.php?pid=3127
题意：给一个矩形长xi，宽yi，给出n个小矩形的长，宽，以及这种小矩形的val，把大矩形分成若干个小矩形，求的最大的val
思路：首先是个 完全背包，然后 是个二维费用背包（长 和 宽）。。注意长宽可交换，每种长宽对应两种分割方法。
如图就是所说的两种方案。
AC代码：
#include<stdio.h>#include<stdlib.h>#include<iostream>#include<cstring>#include<algorithm>using namespace std;const int Max = 20;__int64 dp[1100][1100];struct Two_Cost_Package{ int x; int y; int val;}p[Max];__int64 Tow_Package(int n , int xi , int yi){ memset(dp,0,sizeof(dp)); int i,j,k; for(j = 1;j <= xi;j ++) { for(k = 1;k <= yi;k ++) { for(i = 0;i < n;i ++) { int x = p[i].x; int y = p[i].y; int val = p[i].val; if(j >= x && k >= y) dp[j][k] = max(dp[j][k] , max(dp[j-x][y]+dp[j][k-y] , dp[j-x][k]+dp[x][k-y])+val); swap(x,y); if(j >= x && k >= y) dp[j][k] = max(dp[j][k] , max(dp[j-x][y]+dp[j][k-y] , dp[j-x][k]+dp[x][k-y])+val); } } } return dp[xi][yi];}int main(){ int i,j,k,t,xi,yi,n; scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&xi,&yi); //费用 xi yi for(i = 0;i < n;i ++) scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].val); printf("%I64d\n",Tow_Package(n , xi , yi)); }}