HDU OJ 3127 WHUgirls[DP之背包]

題意：給一個矩形長xi，寬yi，給出n個小矩形的長，寬，以及這種小矩形的val，把大矩形分成若干個小矩形，求的最大的val

思路：首先是個 完全背包，然後 是個二維費用背包（長 和 寬）。。注意長寬可交換，每種長寬對應兩種分割方法。

如圖就是所說的兩種方案。

AC代碼：

[cpp] 
#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)); 
    } 
} 

#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));
    }
}