http://acm.hdu.edu.cn/showproblem.php?pid=3127二維完全背包。
看過背包九講，意識到本題是背包，但開始時沒有把動態方程沒有搞清楚。
f[i][j]表示長i寬j的布能得到的最大價值。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 15
#define LENF 1010
typedef struct
{
int x;
int y;
int c;
}Cut;
Cut ct[LEN];
int f[LENF][LENF];
int N, X, Y;
int Max2(int a, int b)
{
if(a < b)
a = b;
return a;
}
int main()
{
int i, j, k;
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d%d%d", &N, &X, &Y);
for(i = 0; i < N; i++)
scanf("%d%d%d", &ct[i].x, &ct[i].y, &ct[i].c);
memset(f, 0, sizeof(f));
for(i = 1; i <= X; i++)
for(j = 1; j <= Y; j++)
for(k = 0; k < N; k++)
{
int x1 = ct[k].x;
int y1 = ct[k].y;
int c = ct[k].c;
if(i >= x1 && j >= y1)
{
f[i][j] = Max2(f[i][j], f[i - x1][j] + f[x1][j - y1] + c);
f[i][j] = Max2(f[i][j], f[i - x1][y1] + f[i][j - y1] + c);
}
x1 = ct[k].y;
y1 = ct[k].x;
if(i >= x1 && j >= y1)
{
f[i][j] = Max2(f[i][j], f[i - x1][j] + f[x1][j - y1] + c);
f[i][j] = Max2(f[i][j], f[i - x1][y1] + f[i][j - y1] + c);
}
}
printf("%d\n", f[X][Y]);
}
//system("pause");
return 0;
}
posted on 2012-09-04 21:34
小鼠標 閱讀(209)
評論(0) 編輯 收藏 引用 所屬分類:
DP 、
網選訓練