【问题1】某台机器有n个部件组成，每个部件都可以m个不同供应商处购买，已知从j个供应商购买第i个部件的重量和从j个供应商购买第i个部件的价格，求总价格不超过c且重量最小的机器部件购买方案。

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> vWeight;
vector<vector<int>> vPrice;

int nMaxCost;
int n, m;

int nMinWeight = 999;
vector<int> minList;

void BuyComponent(int k, int curCost, int curWeight, vector<int> curList)
{
	if (k > n)
	{
		if (nMinWeight > curWeight)
		{
			nMinWeight = curWeight;
			for (int i = 0; i < curList.size(); i++)
			{
				minList[i] = curList[i];
			}
		}
	}
	else
	{
		for (int j = 0; j < m; j++)
		{
			if (curCost + vPrice[k - 1][j] <= nMaxCost && curWeight < nMinWeight)
			{
				curList[k - 1] = j + 1;
				BuyComponent(k + 1, curCost + vPrice[k - 1][j], curWeight + vWeight[k - 1][j], curList);
			}
		}
	}
}

int main()
{
	cin >> n >> m >> nMaxCost;

	for (int i = 0; i < n; i++)
	{
		vector<int> vWeightLine;
		for (int j = 0; j < m; j++)
		{
			int w;
			cin >> w;
			vWeightLine.push_back(w);
		}
		vWeight.push_back(vWeightLine);
	}

	for (int i = 0; i < n; i++)
	{

		vector<int> vPriceLine;
		for (int j = 0; j < m; j++)
		{
			int p;
			cin >> p;
			vPriceLine.push_back(p);
		}
		vPrice.push_back(vPriceLine);
	}

	vector<int> curList;

	for (int i = 0; i < n; i++)
	{
		curList.push_back(0);
		minList.push_back(0);
	}

	BuyComponent(1, 0, 0, curList);
	cout << endl;
	for (int j = 0; j < n; j++)
	{
		cout << minList[j] << " ";
	}
	cout << endl << nMinWeight << endl;
}

【问题2】有n个城市，用1、2、…、n表示，城市i与城市j之间的距离为dij。有一个货郎要从城市1出发到其他城市一次且仅一次，最后回到城市1，怎样选择行走路线可以使总路程最短？

#include <iostream>
#include <vector>

using namespace std;

const int INF = 9999;

int n;

vector<vector<int>> vCity;

vector<int> vPermCity;

int nCurDistance = 0;

int nMinDistance = INF;

vector<int> minPath;

void swap(int& a, int& b)
{
	int t = a;
	a = b;
	b = t;
}

void SelectPath(int k)
{
	int m = vPermCity.size();

	if (k > m)
	{
		nCurDistance = vCity[0][vPermCity[0] - 1];
		for (int i = 0; i < m - 1; i++)
		{
			nCurDistance += vCity[vPermCity[i] - 1][vPermCity[i + 1] - 1];
		}

		nCurDistance += vCity[vPermCity[m - 1] - 1][0];

		if (nCurDistance < nMinDistance)
		{
			nMinDistance = nCurDistance;
			for (int j = 0; j < m; j++)
			{
				minPath[j + 1] = vPermCity[j];
			}
		}
	}
	else
	{
		for (int j = 0; j < k; j++)
		{
			swap(vPermCity[j], vPermCity[k - 1]);

			SelectPath(k + 1);
			swap(vPermCity[j], vPermCity[k - 1]);
		}
	}
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		vector<int> vDistanceLine;

		for (int j = 0; j < n; j++)
		{
			int d;
			cin >> d;
			vDistanceLine.push_back(d);
		}
		vCity.push_back(vDistanceLine);
	}

	minPath.push_back(1);

	for (int i = 0; i < n - 1; i++)
	{
		vPermCity.push_back(i + 2);
		minPath.push_back(0);
	}
	minPath.push_back(1);

	SelectPath(1);

	for (int j = 0; j < n + 1; j++)
	{
		cout << minPath[j] << " ";
	}
	cout << endl << nMinDistance << endl;
}