import java.util.Arrays;
public class test {
public static void main(String[] args) {
printPlan(new int[]{2900,1800,1800,1500, 1500,1500,1400,1300,1300,1200,1200,1200,1200,400,300,100},3000);
}
/**
* 对要求的木材长度求和sum,初始化一个标准木材的数组source,数组长度为大于sum/standard向上取整
* 对要求的木材长度排序,首先按长度从大到小从标准木材中切割(第一个for循环),第二个for循环从大到小切割剩下的木材
* 对不能切割完的木材递归切割
* @param input
* @param standard
*/
public static void printPlan(int[] input,int standard){
Arrays.sort(input);
double sum=0;
for(int i=0;i<input.length;i++){
sum += input[i];
}
System.out.println("木材长度和："+sum);
int initial = (int)Math.ceil(sum/standard);
System.out.println("共需要木材："+initial+"根");
int[] source = new int[initial];
Arrays.fill(source, standard);
int j = 0;
int[][] a = new int[initial+1][2]; //保存切割的信息数据
int[][] b = new int[initial+1][2]; //保存切割的信息数据
int[][] c = new int[initial+1][input.length]; //保存切割的信息数据
for(int i=0;i<source.length;i++){
j++;
source[i] -= input[input.length-1-i];
System.out.println("从第"+j+"根木材切割"+input[input.length-1-i]+"长度,还剩"+source[i]+"长度");
a[i][0] = j; //保存切割信息
a[i][1] = input[input.length-1-i];
input[input.length-1-i] = 0;
}
for(int i=input.length-initial-1;i>=0;i--){
for(int k=0;k<initial;k++){
if(input[i]<=source[k]){
j++;
source[k] -= input[i];
System.out.println("从第"+(k+1)+"根木材切割"+input[i]+"长度,还剩"+source[k]+"长度");
b[k][0] = k+1; //保存切割信息
b[k][1] = input[i];
input[i] = 0;
break;
}
}
}
if(j==input.length){
System.out.println("全部切割完毕！");
}else if(j<input.length){
System.out.println("还剩下"+(input.length-j)+"根木材没有切割完");
int[] left = new int[input.length-j];
int k = 0;
for(int i=0;i<input.length;i++){
if(input[i]!=0){
left[k] = input[i];
k++;
}
}
printPlan(left,standard);
}
//整理后的信息
for(int i1=0;i1<source.length;i1++){
int j1 = 0;
c[i1][j1] = a[i1][1];
for(int k1=0;k1<initial;k1++){
j1++;
if(a[i1][0]==b[k1][0]){
c[i1][j1] = b[k1][1];
}
}
}
for(int l=0;l<initial;l++){
System.out.println("从第"+(l+1)+"根木材");
for(int i2=0;i2<input.length;i2++)
if(c[l][i2]!=0){
System.out.println("切割"+c[l][i2]+"长度");
}
}
}
}
