剪枝dfs C++写法

解题思路: 最优化剪枝, 记录到达美味度所需要的最小蛋糕数,如果搜索中 达到某一美味度的蛋糕数已经大于book[]数组中所记录的 那么不用再深搜了

注意事项: 都在代码里

参考代码:

#include <bits/stdc++.h>
#define MAX 200010
using namespace std;
typedef long long ll;

int target;
ll books[MAX];  //用来最优化剪枝
typedef pair<int, int> info; //first代表美味程度 second代表这种面包的个数
vector<info> cakes;


void dfs(int cur, int cost) {
	if (cur > target || books[cur] < cost)//最优化剪枝
		return;
	if (cost < books[cur]) {
		books[cur] = cost;
	}
	if (cur == target) return;
	for (int i = cakes.size() - 1; i >= 0; i--)
	{
		if (cakes[i].second == 0 || cakes[i].first + cur > target)
			continue;// 如果该种蛋糕已经被用完 或者使用该种蛋糕后美味度超过了target 
					//就去找还没用完的美味度小的蛋糕
		else {
			cakes[i].second--;
			dfs(cur + cakes[i].first, cost + 1);
			cakes[i].second++;//记得还原状态
		}
	}

}

int main() {
	int n;
	cin >> target >> n;

	for (size_t i = 0; i < n; i++)
	{
		int flavor, num;
		cin >> flavor >> num;
		cakes.push_back(info(flavor, num));
	}
	sort(cakes.begin(), cakes.end());//数据还是排下序  早期可以多用美味度大的蛋糕
	fill(books + 1, books + target + 1, LLONG_MAX);
	dfs(0, 0);
	if (LLONG_MAX != books[target])
		cout << books[target] << endl;
	else
		cout << "><" << endl;
}