【模板】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函数在它们当中选大的那个就可以了

公式中有 ij ,那么这是一个双重循环。

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;
}
作者:Momo·Trace原文地址:https://www.cnblogs.com/momotrace/p/01backpack-problem.html

%s 个评论

要回复文章请先登录注册