01 backpack problem

1. Problem description

Suppose we have a backpack , In front of us i Item , The values of these items are v,
How to pack it can ensure that all the items in the backpack add up to the maximum value .（ Be careful ： One item can only be taken once ）

2. 0/1 What does that mean ？

0 It means that this item is not taken ,1 Take on behalf of this item , In fact, it means taking or not taking

3. analysis

There are three items , Their weights are respectively 1,3,2 Value is ：1,4,3
There is now a capacity of 4 The backpack , How to load can guarantee the maximum total value of the loaded items ？

Item value array : int v[4]={0,1,4,3};
Item weight array : int w[4]={0,1,3,2};
goods :i Package capacity :j It's just a comparison The capacity of the backpack and The weight of the article , There are two cases ：

1. If the capacity of the bag is greater than or equal to the capacity of the article ：j>=w[i]
   Can take , There are two situations at this time , Shall I take it or not , In fact, it is to compare who is of great value , Take the one with high value
   Case one ：
                     Not take ： The value of the last item ( Look straight up at a line ) dp[i-1][j]. for example ： Packet capacity 4, Item is 3 when , Look directly at the previous line value 5.
   The second case ：
                     take ：dp[i-1][j-w[i]]+v[i]. for example ： Packet capacity 2, Item is 3 when ,dp[2-1][2-2]+3=3.
2. If the bag capacity is less than the weight of the item ：j<w[i]
   Can't pack the goods （ Not enough to put down ）, It is equivalent to not installing , The value of not taking is the value of the last item dp[i][j] = dp[i-1][j]
   for example ： Packet capacity 1, The commodity is 2 when , Is the value of the last item 1

if(j>=w[i])// If the capacity of the bag is greater than or equal to the capacity of the article  
	dp[i][j] = max(v[i]+dp[i-1][j-w[i]],dp[i-1][j]);// State transition equation  
else 
	dp[i][j] = dp[i-1][j];// Packet capacity is less than ( Can't fit ) Item capacity , It is equivalent to not installing 

State transition equation ：

 dp[i][j] = max(v[i]+dp[i-1][j-w[i]],dp[i-1][j]);
 
 dp[1][0] ： The capacity of the backpack is 0 when   Installed first 1 Items , How much is it worth 

dp[i][j] = max( Install it , Don't install it ); It is more valuable to install it or not

1. Install it
   v[i]: The value of the object itself
   j-w[i]： Bag capacity minus item capacity
   dp[i-1][j-w[i]]： Go back to the previous line , The maximum value of the remaining Backpack Capacity
2. Don't install it
   dp[i-1][j]： Look straight up at a line

4. Code

#include <iostream>
using namespace std;


int main(){
    
	int v[4]={
    0,1,4,3};// Value of goods  
	int w[4]={
    0,1,3,2};// Item weight  
	int dp[10][10] = {
    0}; // Record status 
	// dp[ i ][ j ]   It means the first one i Item , The capacity of the backpack is  j The greatest value of time   
	for(int i=1;i<4;i++){
    // goods  
		for(int j=1;j<=4;j++){
    // Package capacity  
			if(j>=w[i]){
    // If the capacity of the bag is greater than or equal to the capacity of the article  
				dp[i][j] = max(v[i]+dp[i-1][j-w[i]],dp[i-1][j]);// State transition equation  
			}else dp[i][j] = dp[i-1][j];// Packet capacity is less than ( Can't fit ) Item capacity , It is equivalent to not installing 
			cout<<dp[i][j]<<" "; 
		}
		cout<<endl;
	}
	return 0;
} 

5. Scrolling array

Put two dimensions dp The array is compressed into one dimension dp Array , The scrolling array is used , Every time you run it , Just refresh it dp Array , Make the state transition equation simpler .

use n-1 One dimension of the state dp Array as n A one-dimensional array of states , n A one-dimensional array of states As n+1 A one-dimensional array of states （n+1 And the only n It matters , and n-1 It doesn't matter. .） If you want to install n The maximum value of an item , The list needs to be overwritten （ The list is constantly scrolled and refreshed in this way ）

#include <iostream>
using namespace std;


int main(){
    
	int v[4]={
    0,1,4,3};// Value of goods  
	int w[4]={
    0,1,3,2};// Item weight  
	int dp[10] = {
    0}; // Record status  
	for(int i=1;i<4;i++){
    // goods  
		for(int j=4;j>=1;j--){
    // Reverse push , Use the old data of the previous item 
			if(j>=w[i])
				dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
		}
		for(int k=0;k<=4;k++){
    
			cout<<dp[k]<<" ";
		}
		cout<<endl;
	}
	return 0;
} 

The results are as follows ：

#include <iostream>
using namespace std;


int main(){
    
	int v[4]={
    0,1,4,3};// Value of goods  
	int w[4]={
    0,1,3,2};// Item weight  
	int dp[10] = {
    0}; // Record status 
	for(int i=1;i<4;i++){
    // goods  
		for(int j=4;j>=w[i];j--){
    // Reverse push , Use the old data of the previous item 
			dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	cout<<dp[3];
	return 0;
}