CPP

C++回溯法实例1

最小重量机器设计问题：设某一机器由n个部件组成，每一个部件都可以从m个不同的供应商处购买，设wij是从供应商j处购得的部件i的重量，cij为相应得价格。试设计一个算法，给出总价格不超过c的最小重量机器设计。
#include <iostream.h>
int a[100],b[100],e[100],n,cl,c[100][100],w[100][100],weight, cheap,low,jiage;//b[100]为出售商数量数组
void cheaplow(int i,int j);

void jianzhi()
{
      if(weight>low)
      {
            weight=low;
            jiage=cheap;
            for(int k=1;k<=n;k++)//记录路径
                e[k]=a[k];
      }
      for(int i=n;i>0;i--)//回溯
            if(a!=b)
            {
                cheap-=c[a];
                low-=w[a];
                cheaplow(i,a+1);
            }
            else
            {
                cheap-=c[a];
                low-=w[a];
            }
}

void cheaplow(int i,int j)
{
      if(cheap+c[j]>cl)
      {
            if(j<b) cheaplow(i,j+1);
            else if(i>0)
            {//寻找可以符合条件的节点
                      for(int k=i-1;k>-1;k--)
                      if(a[k]<b[k])
                      {
                         cheap-=c[k][a[k]];
                          low-=w[k][a[k]];
                          cheaplow(k,a[k]+1);
                      }
                      else
                      {
                          cheap-=c[k][a[k]];
                          low-=w[k][a[k]];
                      }
            }
      }
      else
      {
            a=j;
            cheap+=c[j];
            low+=w[j];
            if(i<n)
            {
                cheaplow(i+1,1);
                cheap-=c[j];
                low-=w[j];
            }
            else jianzhi();
      }
}

void main()
{
      int j;
      cout<<"请输入零件个数:";
      cin>>n;
      cout<<"请输入限定钱数:";
      cin>>cl;
      for(int k=1;k<=n;k++)
      {
            cout<<"请输入第"<<k<<"号零件出售商个数:";
            cin>>j;
            b[k]=j;
            for(int l=1;l<=j;l++)
            {
                cout<<"请输入第"<<k<<"号零件价格"<<l<<":";
                cin>>c[k][l];
                cout<<"请输入第"<<k<<"号零件重量"<<l<<":";
                cin>>w[k][l];
                weight+=w[k][l];
                jiage+=c[k][l];
            }//初始的重量和价格都为所有输入之和
      }
      cheaplow(1,1);
      if(jiage<=cl)
      {
            cout<<"价格为"<<jiage<<"时，最轻重量为"<<weight<<endl;
            for(int x=1;x<=n;x++)
                cout<<"零件"<<x<<"在出售商"<<e[x]<<"处购买."<<endl;
      }
      else cout<<"无法找到合适的购买方案!"<<endl;
}