Some understandings about 01 backpacker

01 knapsack

01 knapsack problem

Thinking analysis

1. When we first saw the topic , It's easy to think of using greedy thoughts , Take the most cost-effective items every time .

It is easy to cite counterexamples ：

3 7
6 10 //1.666...
5 8 // 1.6
2 3 //1.5

2. Then we can naturally think of , Since it is not possible to use greedy thoughts , Then enumerate all the selected items , That's the combination .

So we can define the state

\(dfs(i,v,ans)\) It means that I have searched for \(i\) Items , At this time, the total volume of the selected items is \(v\) , The value obtained is \(ans\) .

When we will \(N\) After searching all the items , if \(v \le M\) , Then update our answer .

In the process , We can find out , For a state \(i,v,ans\) , It can come from \(i-1,v,ans\) or \(i-1,v-v_i,（ans-w_i）+w_i\) Turn around ( It corresponds to whether I choose No \(i\) About items ), But because he has the same number of items left , The selected volume is the same , So although it is transferred from two different states , The value obtained is different , But the situation that can be traversed later is the same .

Obviously there is A state of greater value , The result is better than the state with less value .

This is it. Optimal substructural properties , Because this process has the property of optimal substructure , When we carry out the next stage of calculation , It eliminates redundant calculations that are absolutely impossible to be the optimal answer , So we can turn the search into DP, Of course , This process also has No aftereffect principle and Overlapping subproblems .

Briefly explain the optimization of overlapping subproblems . When I already know the state \(dp_{i,v}\) The maximum value that can be obtained , I recorded it , Then traverse to this state , I can directly return to my optimal solution , Instead of continuing to search , Re solve . This requires us DP The problem of has this nature , Otherwise, it is equivalent to no record , There is no optimization .

No aftereffect ensures that the optimal solution I get will not be affected by the later , It must be the best .

3. Just to summarize

state ： \(dp_{i,j}\) Means before \(i\) An object in , The selected volume is \(j\) The items , Get the most value .

State transition equation ：

\(dp[i][j] = \max(dp[i-1][j],dp[i-1][j-v_i]+w_i)\)

code

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int n,m,v[3500],w[3500],dp[12885];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);
	memset(dp,0xcf,sizeof(dp));// The assignment is -INF, Indicates that the status is unreachable , Special attention should be paid here , Cannot be assigned to 0, If the assignment is 0 Words , Then the volume is j The greatest value you can get from your backpack , Contrary to the state we define .
	dp[0]=0;
	for(int i=1;i<=n;i++){
		for(int j=m;j>=v[i];j--){
			dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
		}
	}
	int ans=0;
	for(int i=1;i<=m;i++) ans=max(ans,dp[i]);// Find the best answer .
	cout<<ans<<endl;
	return 0;
}

Well, , Of course , If so 01 Backpacks , use \(dp_{i,j}\) Before presentation \(i\) An object in , With a volume of \(j\) The biggest value you can get from your backpack is also ok Of , But if the topic requires us, we just want to put the volume as \(M\) My backpack is full of , The answer obtained in this state is not necessarily correct .

The code I give is an optimized version , I believe that many bosses speak better than me about the specific process , Here I mainly share one of my thoughts , I hope it can help me consolidate my review , It can also help you understand .

$ \text{-END-}$

\(2022.7.6\)