回溯法最优装载问题（java）

1.问题描述：

有一批共有 n 个集装箱要装上两艘载重量分别为 c1 和 c2 的轮船，其中集装箱 i 的重量为 w[i], 且重量之和小于(c1 + c2)。装载问题要求确定是否存在一个合理的装载方案可将这 n 个集装箱装上这两艘轮船。如果有，找出一种装载方案。

例如，当n=3,c1=c2=50,且w=[10,40,40]时，可将集装箱1和集装箱2装上一艘轮船，而将集装箱3装在第二艘轮船；如果w=[20,40,40],则无法将这3个集装箱都装上轮船。

容易证明，如果一个给定的装载问题有解，则采用如下的策略可以得到最优装载方案。

1.首先将第一艘轮船尽可能装满。

2.将剩余的集装箱装上第二艘轮船。

将第一艘轮船尽可能的装满等价于选取全体集装箱的子集，使该子集中集装箱的重量之和最接近 c1 。因此，等价于一个特殊的　0-1　背包问题。因此是一棵子集树。

max(w1x1+w2x2+...+wixi)

(w1x1+w2x2+...+wixi)<= c1;

xi @{0,1},1<=i<=n

2 算法设计

用回溯法解装载问题时，用子集树表示其解空间显然是最合适的。可行性约束函数可剪去不满足约束条件（

(w1x1+w2x2+...+wixi)<= c1）的子树。在子集树的第j+1层的节点Z处，用cw记当前的装载重量，即cw=(w1x1+w2x2+...+wjxj)，当cw>c1时，以节点Z为根的子树中所有节点都不满足约束条件，因而该子树中解均为不可行解，故可将该子树剪去。

package cn.cb.offer.backtrack;

import javax.swing.*;

import java.util.Scanner;

/**

 * Created by IntelliJ IDEA.

 * User: duanxx

 * email:duanxx@staff.chinabyte.com

 * Date: 13-10-16

 * Time: 下午2:45

 * 最优装载问题回溯法

 */

public class Loading {

    private int n;//集装箱数

    private int[] w;//集装箱重量数组

    private int c;//第一艘轮船的载重量

    private int cw;//当前载重量

    private int bestw;//当前最优载重量

    private int r;//剩余集装箱重量

    private int[] x;//当前解

    private int[] bestx;//当前最优解

    /**

     *

     * @param i

     */

    public void backtrace(int i) {

        //1.到达叶节点

        if (i > n-1) {   //i此时的值=叶节点+1

            if (cw > bestw) {

                for (int j = 0; j < n; j++) {

                    bestx[j] = x[j];

                    bestw = cw;

                }

                return;

            }

        }

        r -= w[i];

        //2.搜索左子树

        if (cw + w[i] < c) {   //x[i =1

            x[i] = 1;

            cw += w[i];

            backtrace(i + 1);

            cw -= w[i];

        }

        //3.搜索右子树

        if (cw + r > bestw) {

            x[i] = 0;

            backtrace(i + 1);

        }

        r += w[i];

    }

    public static void main(String[] args) {

        Loading X = new Loading();

        /*String s1 = JOptionPane.showInputDialog(null, "输入货物数量：",

                "最优装载问题", JOptionPane.QUESTION_MESSAGE);*/

        Scanner scanner = new Scanner(System.in);

        String s1 = scanner.nextLine();

        X.n = Integer.parseInt(s1);

        X.w = new int[X.n];

        X.x = new int[X.n];

        X.bestx= new int[X.n];

        System.out.println("输出货物的重量数组：");

        for (int i = 0; i < X.n; i++) {

            X.w[i] = (int) (100 * Math.random());

            System.out.println(X.w[i]);

        }

        /*String s2 = JOptionPane.showInputDialog(null, "输入第一艘轮船的载重量：",

                "最优装载问题", JOptionPane.QUESTION_MESSAGE);*/

        String s2 = scanner.nextLine();

        X.c = Integer.parseInt(s2);

        for (int i = 0; i < X.n; i++)

            X.r += X.w[i];

        X.backtrace(0);

        System.out.print("输出当前最优解:");

        for (int i = 0; i < X.n; i++) System.out.print(X.bestx[i] + " ");

        System.out.println();

        System.out.println("最优解：" + X.bestw);

    }

}

巴特西

回溯法最优装载问题（java）

最新文章

热门文章