C language to implement the greedy algorithm packing problem
- 2020-04-01 03:44:49
- OfStack
Greedy algorithm is used to find the approximate optimal solution for packing problem
import java.util.Arrays;
import java.util.Comparator;
//Loading problem, greedy algorithm
public class Enchase {
public void test1() {
Integer[] boxs={34,6,40,2,23,12,12};
int boxCaptation=40;//Box capacity
//Reverse order < br / >
Arrays.sort(boxs, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
int unEnchase=boxs.length;//Unpacked number
int minIndex=boxs.length-1;//The smallest bin points to
while (unEnchase>0) {
for(int i=0;i<boxs.length;i++){
//Position box weight zero skip
if(boxs[i]==0){
continue;
}
unEnchase--;
while((boxCaptation-boxs[i])>=boxs[minIndex]){
int k=i+1;
for(;k>i;k++){
//Position box weight zero skip
if(boxs[k]==0){
continue;
}
//Add the box to the original position clear
boxs[i]+=boxs[k];
int temp=boxs[k];
boxs[k]=0;
unEnchase--;
if(boxs[i]>boxCaptation){
//The state restores
when the maximum volume is exceeded
unEnchase++;
boxs[k]=temp;
boxs[i]-=boxs[k];
continue;
}
//Minimum bin update
if(k==minIndex){
for(int y=minIndex;y>0;y--){
if(boxs[y]!=0){
minIndex=y;
}
}
}
break;
}
}
}
}
//Count boxes
int Boxcount=0;
System.out.println(" Packing results: ");
for(int i=0;i<boxs.length;i++){
System.out.print(boxs[i]+"t");
if(boxs[i]==0){
continue;
}
Boxcount++;
}
System.out.println("n Case number :"+Boxcount);
}
public static void main(String[] args) {
new Enchase().test1();
}
}
That's all for this article, I hope you enjoy it.