黑马程序员技术交流社区

标题: 回溯 [打印本页]

---

作者: 何向阳    时间: 2012-12-23 10:51
标题: 回溯
1、问题描述：
     设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设w[j]是从供应商j处购得的部件i的重量，c[j]是相应的价格，给出总价格不超过d的最小重量机器设计。

2、解题思路：
     由于题目已经给出总价格的上限，因此算法通过使用回溯来选择合适的机器使得在总价格不超过d时得到的机器重量最小。首先初始化当前价格cp=0,当前重量cw=0,此外，还要设置一个变量sum表示选择机器的总重量，初始化其为每个部件从1号供应商购买的重量。在循环选择i号机器时，判断从j号供应商购买机器后的价格是否大于总价格，如果不大于则选择，否则不选，继续选择下一供应商进行判断。在得到一个合适的供应商后，继续选择下一机器的供应商，从第一个选到最后一个供应商。当所有机器选择结束后，判断得到的总重量是否比之前的sum小，如果小就赋给sum，然后从这一步开始，回溯到上一机器，选择下一合适供应商，继续搜索可行解，直到将整个排列树搜索完毕。这样，最终得到的sum即为最优解。
     当然，考虑到算法的时间复杂度，还可以加上一个剪枝条件，即在每次选择某一机器时，再判断选择后的当前重量是否已经大于之前的sum，如果大于就没必要继续搜索了，因为得到的肯定不是最优解。

3、算法设计：
a.部件有n个，供应商有m个，分别用w[j]和c[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[j];
         cp+=c[j];
         if(cw<sum && cp<=d)
           backtrack(i+1);
         cw-=w[j];
         cp-=c[j];
     }
}

int main(){
    cin>>n>>m>>d;
    for(int i=1;i<=n;i++){
      for(int j=1;j<=m;j++)
        cin>>c[j];
      sum+=c[1];
    }
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
        cin>>w[j];
    backtrack(1);
    cout<<sum<<endl;
    system("pause");
    return 0;
}

---

作者: 李海鹏    时间: 2012-12-23 11:47
我不是一般的晕……

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2