递归遍历解空间+优化剪枝

解题思路:

01背包问题也就是每样物品有放和不放两种选择的问题。题目要解决的问题是如何组合放入背包的物品来达到价值最大化。

假设共有3件物品，分别选择放、放，不放。那么解可以抽象为（110）；

当然，只有3件物品的话，有2*2*2种不同的组合。

即解空间里包含了8种组合。可以采用递归遍历解空间计算的方法解决问题。

注意事项:
如果不进行优化剪枝的话（优化剪枝：每次进入递归函数后时对当前背包里面体积进行判断，如果大于，则不用考虑后续情况。）数据量大的测试样例会超时。
参考代码:

#include<iostream>
#include<vector>
using namespace std;

#define x first
#define y second
#define pll pair<int,int>

vector<pll>s;
vector<int>pack;
int m;//最大价值
int V;//总体积
int counter;
int cnt_print;

int sum_price()
{
	int sum = 0;
	for (int i = 0; i < pack.size(); ++i)
	{
		if (pack[i] != 0)
			sum += s[i - 1].y;
	}
	return sum;
}

int sum_v()
{
	int sum = 0;
	for (int i = 1; i < pack.size(); ++i)
	{
		if (pack[i] != 0)
			sum += s[i - 1].x;
	}
	return sum;
}

void B(int i, int k)
{
	if (i > s.size())
	{
		/*for (int i = 1; i < pack.size(); ++i)
			cout << pack[i];
		cout << endl;*/
		return;
	}//是否走完

	pack[i] = k;

	if (sum_v() > V)
		return;
	//counter++;

	
	if (sum_price() > m && sum_v() <= V)
		m = sum_price();

	
	B(i + 1, 1);

	if (i + 1 > s.size())
		return;
	B(i + 1, 0);

}


int main()
{
	int n = 0;
	int x1 = 0;
	int y1 = 0;
	cin >> V >> n;

	pack.resize(n + 1, 0);//0号作为根节点
	while (n--)
	{
		cin >> x1 >> y1;
		s.push_back(make_pair(x1, y1));
	}

	B(0, 0);
	cout << m << endl;
	//cout << "counter=" << counter<<endl;
	return 0;
}
/*
3 4
1 2
2 3
3 4
4 5

*/