背包问题

雨点打透心脏的1/2处 2022-05-09 12:14 205阅读 0赞

#### 0-1背包 ####

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    int helper(vector<vector<int>>& dp, vector<int>& need, vector<int>& value,int M) {
        
       int N = need.size();
    
       for(int j=0;j<=M;++j) {
        
          if(j>=need[0])
            dp[0][j] = value[0];
       }
       for(int i=1;i<N;++i) {
        
          for(int j=0;j<=M;++j) {
        
            if(need[i]<=j)
              dp[i][j] = max(dp[i-1][j],dp[i-1][j-need[i]]+value[i]);
            else
              dp[i][j] = dp[i-1][j];
          }
       }
       return dp[N-1][M];
    }
    
    //内存优化
    int helper2(vector<int>& need, vector<int>& value,int M) {
        
       int N = need.size();
       vector<vector<int>> dp(2,vector<int>(M+1,0));
    
       for(int j=0;j<=M;++j) {
        
          if(j>=need[0])
            dp[0][j] = value[0];
       }
       for(int i=1;i<N;++i) {
        
          for(int j=0;j<=M;++j) {
        
            if(need[i]<=j)
              dp[1][j] = max(dp[0][j],dp[0][j-need[i]]+value[i]);
            else
              dp[1][j] = dp[0][j];
          }
          dp[0] = dp[1];Z
       }
       return dp[0][M];
    }
    
    int main() {
        
    
        ios::sync_with_stdio(0);
        cin.tie(0);
    
        int N = 0,M = 0;
        cin >> N >> M;
        vector<int> need,value;
        for(int i=0;i<N;++i) {
        
            int a,b;
            cin >> a >> b;
            need.push_back(a);
            value.push_back(b);
        }
    
        // vector<vector<int>> dp(N,vector<int>(M+1,0));
        // int res = helper(dp,need,value,M);
        int res = helper2(need,value,M);
        cout << res << endl;
        return 0;
    }

#### 完全背包 ####

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    int helper(vector<int>& need,vector<int>& value,int M) {
        
    	int N = need.size();
    	vector<vector<int>> dp(2,vector<int>(M+1,0));
    	for(int j=0;j<=M;++j) {
        
    		if(j>=need[0])
    			dp[0][j] = dp[0][j-need[0]] + value[0];
    	}
    
    	for(int i=1;i<N;++i) {
        
    		for(int j=0;j<=M;++j) {
        
    			if(j>=need[i])
    				dp[1][j] = max(dp[0][j],dp[1][j-need[i]]+value[i]);
    			else
    				dp[1][j] = dp[0][j];
    		}
    		dp[0] = dp[1];
    	}
    	return dp[1][M];
    }
    
    int main() {
        
    	ios::sync_with_stdio(0);
    	cin.tie(0);
    
    	int N = 0,M = 0;
        cin >> N >> M;
        vector<int> need,value;
        for(int i=0;i<N;++i) {
        
            int a,b;
            cin >> a >> b;
            need.push_back(a);
            value.push_back(b);
        }
    
        int res = helper(need,value,M);
        cout << res << endl;
    
    	return 0;
    }