今天想要分析的也是一道用回溯法搜索排列树的问题。
1、问题描述:
设某一机器由n个部件组成,每一种部件都可以从m个不同的供应商处购得。设w[i][j]是从供应商j处购得的部件i的重量,c[i][j]是相应的价格,给出总价格不超过d的最小重量机器设计。
2、解题思路:
由于题目已经给出总价格的上限,因此算法通过使用回溯来选择合适的机器使得在总价格不超过d时得到的机器重量最小。首先初始化当前价格cp=0,当前重量cw=0,此外,还要设置一个变量sum表示选择机器的总重量,初始化其为每个部件从1号供应商购买的重量。在循环选择i号机器时,判断从j号供应商购买机器后的价格是否大于总价格,如果不大于则选择,否则不选,继续选择下一供应商进行判断。在得到一个合适的供应商后,继续选择下一机器的供应商,从第一个选到最后一个供应商。当所有机器选择结束后,判断得到的总重量是否比之前的sum小,如果小就赋给sum,然后从这一步开始,回溯到上一机器,选择下一合适供应商,继续搜索可行解,直到将整个排列树搜索完毕。这样,最终得到的sum即为最优解。
当然,考虑到算法的时间复杂度,还可以加上一个剪枝条件,即在每次选择某一机器时,再判断选择后的当前重量是否已经大于之前的sum,如果大于就没必要继续搜索了,因为得到的肯定不是最优解。
3、算法设计:
a.部件有n个,供应商有m个,分别用w[i][j]和c[i][j]存储从供应商j 处购得的部件i的重量和相应价格,d为总价格的上限。
b.用递归函数backtrack(i)来实现回溯法搜索排列树(形式参数i表示递归深度)。
① 若cp>d,则为不可行解,剪去相应子树,返回到i-1层继续执行。
② 若cw>=sum,则不是最优解,剪去相应子树,返回到i-1层继续执行。
③ 若i>n,则算法搜索到一个叶结点,用sum对最优解进行记录,返回到i-1层继续执行;
④ 用for循环对部件i从m个不同的供应商购得的情况进行选择(1≤j≤m)。
c.主函数调用一次Knapsack(1)即可完成整个回溯搜索过程,最终得到的sum即为所求最小总重量。
4.算法时间复杂度:
程序中最大的循环出现在递归函数backtrack(i)中,而此函数遍历排列树的时间复杂度为O(n!),故该算法的时间复杂度为O(n!)。
5.
#include<iostream>
#define N 1000
using namespace std;
int n,m,d,cp=0,cw=0,sum=0;
int c[N][N],w[N][N];
void backtrack(int i){
if(i>n){
if(cw<sum)
sum = cw;
return ;
}
for(int j=1;j<=m;j++){
cw+=w[i][j];
cp+=c[i][j];
if(cw<sum && cp<=d)
backtrack(i+1);
cw-=w[i][j];
cp-=c[i][j];
}
}
int main(){
cin>>n>>m>>d;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
cin>>c[i][j];
sum+=c[i][1];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>w[i][j];
backtrack(1);
cout<<sum<<endl;
system("pause");
return 0;
}
分享到:
相关推荐
分支限界法之最小重量机器设计问题 这个算法有些难以理解 主要是你得搞清楚优先级队列的使用 该代码注释详细
全都是自己写的,都能跑出来 实打实写的哦~ ...3、用c++语言实现用回溯法、分支限界法解决最小重量机器设计问题,分析时间复杂性; 4、体会回溯法、分支限界法解决问题的基本思路和步骤。 预览地址:
利用C++实现最小重量机器设计问题,通过input.txt文件输入数据,最终的结果输出到output.txt文件中,对该过程有较好的理解
最小重量机器设计问题.cpp
经典算法,最小机器设计问题的C语言代码实现 所属课程:算法分析与设计
试设计一个算法,给出总价格不超过cost的最小重量机器设计。 Input 每组测试数据第一行有3 个正整数n,m和cost。接下来的2n行,每行m个数。前n行是cij,后n行是wij。(1,m; 1; 1, 1) Output 分2行输出最小重量,...
1、子序列和 问题描述: 给定整数a1、a2、..... (1) 。推断能否 够从中选出若干数,使它们的和恰好为k。...-个算法,给出总价格不超过cost的最小重量机器设计, 可以在同 一个供应商处购得多个部件。
4.最小重量机器设计问题。设某一机器由n个部件组成,每一种部件可以从m个不同的供应商处购得。设wij是从供应商j处购得的部件i的重量,cij是相应的价格。试设计一个算法,给出总价格不超过c的最小重量机器设计。
用队列式优先级的分支限界方法,实现最小机器重量设计问题
试设计一个算法,给出总价格不超过c的最小重量机器设计。 40、 设有n件工作分配给n个人。为第i个人分配工作j所需的费用为ci,j 。试设计一个算法,计算最佳工作分配方案,为每一个人都分配1 件不同的工作,并使总费用...
1.Problem A:子集树问题 2.:0-1 Knapsack 3.排列树问题 4.图的m可着色优化问题 5.子集和问题 6.最小重量机器设计问题 7.General Search . . .
3.1.3 AT89C51的最小系统电路构成 3.2 电源电路设计 3.3 数据采集部分电路设计 3.3.1 传感器和其外围以及放大电路设计 3.3.2 A/D转换芯片与AT89C51单片机接口电路设计 3.3.3 测量算法 3.4 显示电路与AT89C51单片机...