設(shè)某一機(jī)器由n個(gè)部件組成，每一種價(jià)格都可以從m個(gè)不同的供應(yīng)商處購(gòu)得。設(shè)wij是從供應(yīng)商j處購(gòu)得的部件i的重量，cij是相應(yīng)的價(jià)格。 試設(shè)計(jì)一個(gè)算法，給出總價(jià)格不超過(guò)d的最小重量機(jī)器設(shè)計(jì)。

分析：

供應(yīng)商為m，這是一個(gè)m叉樹(shù)，邏輯倒不是很難，就是記錄部件從哪個(gè)廠商購(gòu)得時(shí)，注意一下即可。

代碼：

#include<stdio.h>
#define n 3    //部件數(shù)
#define m 3    //供應(yīng)商
#define d 4    //總價(jià)格不超過(guò)d
int w[n][n]={1,2,3,3,2,1,2,2,2},c[n][n]={1,2,3,3,2,1,2,2,2}; 
int a[n]={0},final[n]={0}; //final記錄部件的最終供應(yīng)商，a記錄過(guò)程中的供應(yīng)商 
int minweight=1000000;      //最終的最小質(zhì)量
int weight=0,value=0;     //兩個(gè)過(guò)程值
void traceback(int t){
    if(t==3&&value<=d){
        if(weight<minweight){
            minweight=weight;
            for(int k=0;k<n;k++){
                final[k]=a[k];
            }
        } 
        return;
    }
    if(value<=d){
        for(int i=0;i<m;i++){  //遍歷的是供應(yīng)商 
            a[t]=i; //記錄一下當(dāng)前的這個(gè)部件是從哪個(gè)供應(yīng)商購(gòu)得
            weight+=w[t][i];    
            value+=c[t][i];
            traceback(t+1);
            value-=c[t][i];
            weight-=w[t][i];
            a[t]=0;
        }
    }
} 

int main(){
    traceback(0);           //t代表部件 
    printf("最小重量是%d\n",minweight); 
    for(int i=0;i<n;i++)
        printf("%3d",final[i]+1);
    printf("\n");   
    return 0;
} 

運(yùn)行截圖