Dynamic programming knapsack problem -- 01 knapsack

2022.7.20
         Summary of the theme ： Yes n Items And a Capacity of p The backpack , Each item has weight w and value v Two properties , It is required to select several items to put into the backpack, so that the total value of the items in the backpack is the largest, and the total weight of the items in the backpack does not exceed the capacity of the backpack . 

         In the above example , Because each object has only two possible states （ Take or not ）, Corresponds to... In binary 0 and 1, This kind of problem is called 「0-1 knapsack problem 」. 

         We use two-dimensional arrays dp[i][j] It means to put it in front only i When items , The capacity of the backpack does not exceed j The greatest value of time . Dynamic transfer equations can be listed dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]).

for(int i=1;i<=n;i++){
		for(int j=p;j>=w[i];j--){
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
		}
	}

        But open dp[n][p] Your space will MLE, So we're going to use a scrolling array , Get the dynamic transfer equation , Delete one dimension , Keep right dp[i][j] Influential i（ Quantity of articles ）dp[j]=max(dp[j],dp[j-w[i]]+v[i]).

for(int i=1;i<=n;i++){
	for(int j=p;j>=w[i];j--){
		f[j]=max(f[j],f[j-w[i]]+v[i]);
	}
}

         Be careful , We traverse from back to front , Because for the currently processed items i And the current state dp[i][j], stay j>=w[i] when ,dp[i][j] Yes, it will be dp[i][j-w[i]] Affected by . This is equivalent to items    It can be put into the backpack many times , It doesn't agree with the question . To avoid that , We can change the order of enumeration , from p Enumerate to w[i], In this way, the above errors will not occur , because dp[i][j] Always in dp[i][j-w[i]] Updated before .

Real exercises ：（ Information Science Olympiad all in one 1267：【 example 9.11】01 knapsack problem ）

Title Description ：

         A traveler has one that can hold up to  MM  Kilogram backpack , Now there is  n  Item , Their weights are W1,W2,...,Wn, Their values are C1,C2,...,Cn, Ask travelers to get the maximum total value .

Input format ：

         first line ： Two integers ,M( Backpack Capacity ,M<=200) and N( Quantity of articles ,N<=30); The first 2..N+1 That's ok ： Two integers per line Wi,Ci, Indicates the weight and value of each item .

sample input ：

10 4
2 1
3 3
4 5
7 9

sample output ：

12

Ideas ：

This is a template question .

Code ：

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <fstream>
#include <sstream>
#include <vector>
#include <string>
#include <cstdio>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <list>
#include <map>
#define int long long
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int p,n,w[40],c[40],f[400];
signed main(){
	cin >>p>>n;
	for(int i=1;i<=n;i++){
		cin >>w[i]>>c[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=p;j>=w[i];j--){
			f[j]=max(f[j],f[j-w[i]]+c[i]);
		}
	}
	cout <<f[p];
	return 0;
}