hdu 3127 完全背包 二維限制條件 放置順序相關性
來源：程序員人生 發布時間：2015-04-01 07:50:57 閱讀次數：2731次
背景：這個題實在沒法，看的題解的思路，確切很難想到。也算明白了背包問題只是母題，其生的兒子，常常找不出來原來的母親了。
思路：把矩形的長和寬兩個參數看作完全背包的限制條件，所以在選取每個物品的時候操作的都不再是以為數組，而是2維數組。切割方式就是當前選擇的物品作為第1個矩形，在大矩形的右下角切，有4種情況。這個題的最大的注意點是：1般的完全背包問題，對物品的選擇順序是沒有要求的，所以限制條件的循環和物品選擇的循環是可以互換的，但是這個題，對每個大矩形，在右下角首先選擇哪個物品作為第1個物品是有影響的，所以把物品選擇循環設為內循環，沒有次都對n個物品做第1個物品做判斷。
學習：1.既然有可能遇見對選擇順序有要求的完全背包問題，而且順序是不是有影響本身就是很難判斷的，那末以后就統1把物品循環放在內循環。
我的代碼：
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int F[1009][1009],w[10][3];
int main(void){
int t,n,x,y;
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&n,&x,&y);
for(int i=0;i < n;i++) scanf("%d%d%d",&w[i][0],&w[i][1],&w[i][2]);
memset(F,0,sizeof(F));
for(int i=0;i <= x;i++)
for(int j=0;j <= y;j++){
for(int k=0;k < n;k++){
if(w[k][0] <= i && w[k][1] <= j){
F[i][j]=max(F[i][j],F[i-w[k][0]][j]+F[w[k][0]][j-w[k][1]]+w[k][2]);
F[i][j]=max(F[i][j],F[i][j-w[k][1]]+F[i-w[k][0]][w[k][1]]+w[k][2]);
}
swap(w[k][0],w[k][1]);
if(w[k][0] <= i && w[k][1] <= j){
F[i][j]=max(F[i][j],F[i-w[k][0]][j]+F[w[k][0]][j-w[k][1]]+w[k][2]);
F[i][j]=max(F[i][j],F[i][j-w[k][1]]+F[i-w[k][0]][w[k][1]]+w[k][2]);
}
swap(w[k][0],w[k][1]);
}
}
printf("%d
",F[x][y]);
}
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
