【模板】01背包问题

一个在旅途中的长者有一个最多能用\(M\)公斤的背包，现在有\(n\)件物品，它们的重量分别是\(W1，W2，...,Wn\),它们的价值分别为\(C1,C2,...,Cn\).求旅行者能获得最大总价值。

输入

• 第1行：两个整数，\(M\)（背包容量，\(M\le200\)）和\(n\)（物品数量，\(n\le30\)）；

• 第\(2\)至\(n+1\)行：每行两个整数\(Wi\),\(Ci\)，表示每个物品的重量和价值。

输出

• 仅一行，一个数，表示最大总价值。

样例

样例输入1

10 4
2 1
3 3
4 5
7 9

样例输出1

12

解析

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

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

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

其中 d 数组表示当前容量可以装的最大价值，w[i] 是重量，c[i] 是价值。

在公式中，我们在装和不装中选一种：

1. 不装：就是当前的最大重量 d[j]

2. 装：先在当前容量 j 中给 当前重量 w[i] 预留一个位置 （d[j-w[i]]），然后在加上当前价值 c[i]

最后，用max函数在它们当中选大的那个就可以了

公式中有 i 有 j ，那么这是一个双重循环。

Code

#include <bits/stdc++.h>                 
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[v]; //注意不是d[n] 
	return 0;
}