子问题定义: 定义p[i][j]为布料宽为i，高为j的最优产出，每次剪下一块布料，剩余布料最多形成三块矩阵面料。每次剪裁会有两种情况，水平切割布料，其次是将布料旋转90度后在切割布料。
递归关系:
初值设定：
p[0][h]=0
p[w][0]=0
求解顺序：
依次求解二维数组p的每一行，每一列，最终的结果为p[布料的宽][布料的高]
package org.xiu68.ch6.ex8;
public class Ex6_14 {
//布料剪裁问题
public static void main(String[] args) {
// TODO Auto-generated method stub
Clothing[] cloths=new Clothing[]{
new Clothing(10,10,10),
new Clothing(20,20,10),
new Clothing(30,30,30),
new Clothing(40,40,160)
};
tailor(10,10,cloths); //生产出的产品最高价为: 10
tailor(40,40,cloths); //生产出的产品最高价为: 160
Clothing[] cloths2=new Clothing[]{
new Clothing(10,10,10),
new Clothing(10,10,11),
new Clothing(20,20,10),
new Clothing(30,30,30),
new Clothing(40,40,180)
};
tailor(10,10,cloths2); //生产出的产品最高价为: 11
tailor(40,40,cloths2); //生产出的产品最高价为: 180
}
/*
* w:布料的宽
* h:布料的高
* cloths:服装产品
* 一块布切割后，最多剩下3块
*/
public static void tailor(int w,int h,Clothing[] cloths){
if(w<=0 || h<=0)
return;
int[][] p=new int[w+1][h+1]; //p[i][j]表示布料宽为i，高为j所得到的最大价格
//求布料的宽为i，高为j所得到的最大价格
for(int i=1;i<=w;i++){
for(int j=1;j<=h;j++){
p[i][j]=0;
for(int k=0;k<cloths.length;k++){
int kWidth=cloths[k].width, //第k件服装的需要布料的宽
kHeight=cloths[k].height, //第k件服装的需要布料的高
kPrice=cloths[k].price, //第k件服装的价格
horizontalCut=0, //水平切割布料所得到的最大价格
verticalCut=0; //旋转布料90度后再切割布料所得到的最大价格
if(i>=cloths[k].width && j>=cloths[k].height) //水平切割
horizontalCut=kPrice+p[kWidth][j-kHeight]+p[i-kWidth][kHeight]+p[i-kWidth][j-kHeight];
if(i>=cloths[k].height && j>cloths[k].width) //旋转布料90度后再切割
verticalCut=kPrice+p[kHeight][j-kWidth]+p[i-kHeight][kWidth]+p[i-kHeight][j-kWidth];
if(horizontalCut>verticalCut){
if(horizontalCut>p[i][j])
p[i][j]=horizontalCut;
}else{
if(verticalCut>p[i][j])
p[i][j]=verticalCut;
}
}//for3
}//for2
}//for1
System.out.println("生产出的产品最高价为: "+p[w][h]);
}
}
//服装
class Clothing{
public int width; //宽
public int height; //高
public int price; //价格
public Clothing(int width, int height, int price) {
super();
this.width = width;
this.height = height;
this.price = price;
}
}