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

超、凢脫俗 2022-11-17 03:58 147阅读 0赞

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:\[email protected\]

\* 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最优解,回溯法最优装载问题（java）

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关【贪心算法】最优装载问题C++语言

相关算法设计与分析——贪心算法——最优装载问题

相关回溯法解旅行商问题java,【算法作业】用回溯法求解旅行商问题

相关回溯法装载问题java最优解,回溯法最优装载问题（java）

相关装载问题-回溯法

相关贪心算法（最优装载问题）

相关最优装载问题（贪心基础）

相关回溯法解组合问题——硬币问题

相关贪心算法1：贪心的概念最优装载问题

相关回溯法总结+四个小例题(装载问题，01背包，n后，最大团，m着色)