关于我写了个装载问题的野鸡算法的那档事

由于原来的（书上的）算法我实在是看不懂…所以我想仿照我之前解决全排列的思路（逐个选择法）解决这个问题

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import java.util.Arrays;

public class Loading {

    static int[] w={5,2,1,3};
    int n=4,c1=10,cw=0,bestw=0;
    static int[] isVisit=new int[w.length];

    /***
     *
     * @param c1 第一艘船的最大载重
     * @param w 数组，用于记录每件货物的重量
     * @param cw 当前最大载重
     * @param bestw 最佳载重
     * @param isVisit 整形数组（相当于解空间的其中一个解），若将货物搬上第一艘船，则用1表示，否则置为0，数组一开始初始化值均为0，表示还没货物上船
     * @param index 从第几号货物开始，然后按照顺序决定是否将其搬上船
     * @return
     *
     * 另外这代码的返回值是bestw，如果在某个阶段找到了bestw，则在回溯的时候bestw会被一直保留，在回溯的过程中bestw也有可能被替换
     * 唯一的缺陷就是，在回溯的过程找到了最佳bestw无法单独打印出来，截图的效果就是缺陷，最后一种装载方案就是最佳的装载方案
     */
    public static int loading(int c1,int[] w,int cw,int bestw,int[] isVisit,int index){
        for(int i=index;i<w.length;i++) {
            if (isVisit[i]!=1&&(cw+w[i]<=c1)){//如果当前货物A没上船并且（当前最大载重＋A的重量）＜第一艘船的最大载重
                isVisit[i]=1;//A货物上船
                cw+=w[i];//改变当前载重
                if(cw>bestw){//如果当前载重＞最佳载重，则更新最佳载重
                    bestw=cw;
                    System.out.println(Arrays.toString(isVisit));
                }
                else{//如果没有则直接返回，结束返回上一级函数
                    return bestw;
                }
                bestw=loading(c1,w,cw,bestw,isVisit,index+1);
                cw-=w[i];
                isVisit[i]=0;

            }
        }
        //System.out.println(Arrays.toString(container));
        return bestw;
    }

    public static void main(String[] args) {
        int[] w={5,2,1,3};
        int c1=10,cw=0,bestw=0;
         int[] container=new int[w.length];
       int bw= Loading.loading(c1,w,cw,bestw,isVisit,0);
       System.out.println("第一艘货船最多能载的货物重量为"+bw);
       System.out.println("其中最后一种装载方案是最优的...");
    }
}

最后的结果截图（也是这段代码最大的问题…虽然结果对了）