【模板】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;
}

本文來自小默的博客，轉載請註明原文鏈接：https://www.cnblogs.com/momotrace/p/01backpack-problem.html