麦芽雪冷萃

题目描述：

设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设是从供应商j处购得的部件i的重量，是相应的价格。试着设计一个算法，给出总价格不超过c的最小重量机器设计。

输入描述：

第1行有3个正整数n, m, d。接下来的2n行，每行n个数，前n行是c，后n行是w。

输出描述：

第1行输出计算出来的最小重量，第2行输出每个部件的供应商。

输入样例：

3 3 4
1 2 3
3 2 1
2 2 2
1 2 3
3 2 1
2 2 2

输出样例：

4
1 3 1

解题思路：

用回溯法进行求解，若当前选择方案的总重量小于最小重量就对最佳方案和最小总重量进行更新。

代码：

#include <bits/stdc++.h>
using namespace std;
#define Up(i,a,b) for (int i = a; i <= b; i++)
#define ms(a,x) memset(a,x,sizeof(a))
const int INF = 0x3f3f3f3f;
const int maxn = 101;
int n,m,d;    //n个部件,m个供应商,总价不超过d
int v[maxn][maxn];    //v[i][j]表示从供应商j处购得部件i的价格
int w[maxn][maxn];    //w[i][j]表示从供应商j处购得部件i的重量
int best[maxn];    //best[i]表示部件i的最佳选择方案
int minW = INF;   //最小重量
int cur[maxn];    //当前的选择方案
int curW = 0;     //当前总重量
int curV = 0;     //当前重价值
void traceback(int x)
{
    if(x > n)
    {
        if(curW < minW)
        {
            minW = curW;    //更新最小重量
            Up(i,1,n)
            {
                best[i] = cur[i];    //更新最佳选择方案
            }
        }
    }
    else
    {
        Up(i,1,m)
        {
            cur[x] = i;
            curW += w[x][i];
            curV += v[x][i];
            if(curW<=minW && curV<=d)
            {
                traceback(x+1);
            }
            curW -= w[x][i];
            curV -= v[x][i];
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    ms(cur,0);
    ms(best,0);
    cin >> n >> m >> d;
    Up(i,1,n)
    {
        Up(j,1,m)
        {
            cin >> v[i][j];
        }
    }
    Up(i,1,n)
    {
        Up(j,1,m)
        {
            cin >> w[i][j];
        }
    }
    traceback(1);    //回溯,入口为第1个部件
    cout << minW << endl;
    Up(i,1,n)
    {
        cout << best[i] << (i==n?"\n":" ");
    }
    return 0;
}