背包问题

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;
}