/回溯法#include <iostream>#include<fstream>#include <vector>#include <algorithm>#define MAX 100using namespace std;int w[MAX][MAX]; //从供应商j处购买部件i的重量int c[MAX][MAX]; //从供应商j处购买构件i的价格int bestx[MAX]; //储存第i个部件的最佳供应商编号int x[MAX]; //记录求解过程中储存第i个部件的供应商编号 int n, m, d; //部件个数，供应商个数，最大总价格 int cw = 0, cc = 0, bestw = 99999; //当前已选部件的重量，当前已选部件的价格，最小重量 void Input(const string &input_filename){ ifstream fin(input_filename); fin >> n >> m >> d; //从文件第一行读取n，m，d for (int i = 1; i <= n; i++) { //从前n行读取每个商品在每个供应商处的价格 for (int j = 1; j <= m; j++) { fin >> c[i][j]; } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { fin >> w[i][j]; //从后n行读取每个商品在每个供应商处的重量 } } fin.close();}void Output(const string &output_filename) //将运行结果保存至文本文件“output.txt” { ofstream fout("output.txt"); fout << "最小重量为：" << bestw << endl; fout << "每个部件的供应商：" << endl; for (int i = 1; i <= n; i++) fout << bestx[i] << " "; fout << endl; fout.close();}void BackTrack(int t) //利用回溯法求解，在总价格<=d的条件下计算第t-n个部件的最小重量 { if (t > n) //已经到叶子结点(所有节点选择完毕) { if(cw<bestw) //当前重量和小于最小重量 { bestw = cw; //更新最优解 for (int i = 1; i <= n; i++) bestx[i] = x[i]; //更新每个部件对应的供应商编号 } return; } else { if(cw + w[t][i] > bestw) return; for (int i = 1; i <= m; i++) { //循环处理m个供应商 if (cc + c[t][i] <= d && cw + w[t][i] < bestw) //限界函数：当前已选部件的价格加从第i个供应商处买第t个部件的价格之和小于最大总价格,剪枝函数：当前已选部件的价格加从第i个供应商处买第t个部件的价格之和小于最大总价格 { x[t] = i; //记录当前部件t的供应商编号 cc += c[t][i]; //选中t部件，将t部件对应重量、价格加到已选部件的总价格、总重量 cw += w[t][i]; BackTrack(t + 1); //继续深入t的子节点 } cc -= c[t][i]; //子节点遍历完成，回溯之前要将重量及价格恢复原值 cw -= w[t][i]; } }}void Complex(){ // 读取输入数据 std::ifstream inputFile("input.txt"); int n; inputFile >> n; std::vector<int> serviceTimes(n); for (int i = 0; i < n; ++i) { inputFile >> serviceTimes[i]; } inputFile.close(); // 对顾客的服务时间进行排序 std::sort(serviceTimes.begin(), serviceTimes.end()); // 初始化等待时间 int totalWaitTime = 0; int currentWaitTime = 0; // 计算等待时间 for (int serviceTime : serviceTimes) { currentWaitTime += serviceTime; totalWaitTime += currentWaitTime; } // 计算平均等待时间 double averageWaitTime = static_cast<double>(totalWaitTime) / n; // 将结果写入输出文件 std::ofstream outputFile("output.txt",ios::app); outputFile <<"时间复杂度:" <<averageWaitTime<<"s"; outputFile.close();}int main() { Input("input.txt"); BackTrack(1); Output("output.txt"); Complex(); return 0;}
5-3
最小重量机器设计问题。
问题描述：设某一机器由n个部件组成，每种部件都可以从m个不同的供应商处购得。设w是从供应商j处购得的部件i的重量，ci是相应的价格。试设计一个算法，给出总价格不超过c的最小重量机器设计。
算法设计：对于给定的机器部件重量和机器部件价格，计算总价格不超过d的最小重量
机器设计。
数据输入：由文件input.txt 给出输入数据。第一行有3个正整数n、m和d。接下来的
2n行，每行n个数。前n行是c，后n行是w。
结果输出：将计算的最小重量及每个部件的供应商输出到文件output.txt。
输入文件示例
input.txt
334 123 321 222 123 321 222
运行错误，只有输入事例可以运行，改变数据就运行不了，望dl改正指教
