两道关于回溯法,分支限界法的算法题

发布时间:2017-6-27 2:52:37 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"两道关于回溯法,分支限界法的算法题 ",主要涉及到两道关于回溯法,分支限界法的算法题 方面的内容,对于两道关于回溯法,分支限界法的算法题 感兴趣的同学可以参考一下。

1.最小重量机器设计问题:设某一机器由n个部件组成,每一种部件都可以从m个不同的供应商处购得。设 wij    是从供应商j处购得的部件 i 的重量, cij 是相应的价格。试设计一个算法,给出总价格不超过 c 的最小重量机器设计。

方法一:回溯法设计:

import static org.junit.Assert.*;import java.util.Scanner;import org.junit.Test;public class 最小重量机器 {        /*     * 3 3     * 3 2  1 4  5 6     * 1 4  3 2  5 6     * 5 6  3 2  1 4     * 10     *      * 答案是5     */    private static int w[][];    private static int c[][];    private static int vis[][];    private static int n, m, cc;    private static int ans;    private static Scanner cin;    static{        cin = new Scanner(System.in);    }    private static void init() {        for(int i = 0; i < n; i++){            for(int j = 0; j < m; j++){                vis[i][j] = 0;            }        }        ans = Integer.MAX_VALUE;    }    public static void main(String[] args) {        System.out.println("请输入部件数目以及供货商数量n和m:");        n = cin.nextInt();        m = cin.nextInt();        w = new int[n][m];        c = new int[n][m];        vis = new int[n][m];        System.out.println("n行代表n个部件,每行输入每个供货商供应此部件的重量以及价格:");        for(int i = 0; i < n; i++){            for(int j = 0; j < m; j++){                w[i][j] = cin.nextInt();                c[i][j] = cin.nextInt();            }        }        System.out.println("请输入不超过的价格p:");        cc = cin.nextInt();        init();        work(0, cc, 0, 0);        if(ans == Integer.MAX_VALUE){            System.out.println("不能找出总价格不超过 c的最小重量机器的方案");        }else{            System.out.println("满足方案的最小重量是:" + ans);        }    }    private static void work(int i, int cc, int ww, int p){        if(i == n){            if(p <= cc){                ans  = Math.min(ans, ww);            }            return;        }        for(int j = 0; j < m; j++){            vis[i][j] = 1;            work(i + 1, cc, ww + w[i][j], p + c[i][j]);            vis[i][j] = 0;

上一篇:python中__init__.py文件的作用
下一篇:无法嵌入互操作类型“Microsoft.Office.Interop.Excel.ApplicationClass”请改用适用的接口

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。