C++ 背包问题——01背包

01背包问题是所有背包问题的基础，只有学好01背包，才能掌握背包问题。

01背包：“01”表示只能取或者不取，下面看例题：

【题目描述】

【输入】

【输出】

【输入样例】

10 4
2 1
3 3
4 5
7 9

【输出样例】

12

好了，这是一个经典的01背包问题

做01背包问题只要记住一个公式：

d[j]=max(d[j],d[j-w[i]]+c[i]；

公式中有 i 有 j ，那么这是一个双重循环，w 数组表示重量，c 数组表示价值。

完整的c++代码如下：

#include 
using namespace std;
int v,n,d[2000],c[50],w[50]; //d数组的下标表示容量
int main()
{
	cin >>v >>n; //v表示容量，n表示数量 
	for (int i=1;i<=n;i++)
		cin >>w[i] >>c[i];
	for (int i=1;i<=n;i++) 
		for (int j=v;j>=w[i];j--)  //01背包中，第二重循环要倒序，从v到w[i] 
		{
			d[j]=max(d[j],d[j-w[i]]+c[i]);  //公式 
		}
	cout <//注意不是d[n] 
	return 0;
}

这些东西只要背下来就行了，非常简单。