本文主要是介绍回溯法 最小重量机器设计，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
描述 设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设wiy 是从供应商j 处购得的部件i的重量,ciy是相应的价格。试 设计一个算法，给出总价格不超过c的最小重量机器设计。
对于给定的机器部件重量和机器部件价格， 编程计算总价格不超过d的最小重量机器设计。
输入
第一行有3 个正整数n ，m和d。接下来的2n 行，每行n个数。前n行是c，后n行是w。
输出
将计算出的最小重量，以及每个部件的供应商
样例输入
3 3 4
1 2 3
3 2 1
2 2 2
1 2 3
3 2 1
2 2 2
样例输出
4
1 3 1
import java.util.Scanner;public class MinWeightMachine {static int n = 0; // 部件数static int m = 0; // 厂商数static int d = 0; // 最大价格static int[][] c; // 部件 i 厂商 j 的价格static int[][] w; // 部件 i 厂商 j 的重量static int cT = 0; // 当前总价格static int wT = 0; // 当前总重量static int bestw; // 当前最小重量static int[] bestx;static int[] savex;public static void main(String[] args) {Scanner input = new Scanner(System.in);n = input.nextInt();m = input.nextInt();d = input.nextInt();c = new int[n][m]; // i j 部件 i 厂商 jw = new int[n][m];bestx = new int[m];savex = new int[m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {c[i][j] = input.nextInt();}}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {w[i][j] = input.nextInt();}}input.close();machinePath(0);System.out.println(bestw);for (int j = 0; j < n; j++){System.out.print(savex[j]+" ");}}public static void machinePath(int i) { // 部件 i 厂商 j i<n j<mif (i >= n) {if (cT < bestw || bestw == 0) {bestw = cT;for (int j = 0; j < n; j++){savex[j] = bestx[j];}}return;}for (int j = 0; j < m; j++) {if (cT + c[i][j] <= d) {cT += c[i][j];wT += w[i][j];bestx[i]=j+1;machinePath(i + 1);bestx[i]=0;cT -= c[i][j];wT -= w[i][j];}}}}
这篇关于回溯法 最小重量机器设计的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
