2. 01背包问题 - AcWing题库

DP做题思路分析

 

实现代码：

#include <iostream>
#include <algorithm>using namespace std;const int N = 1010;int n , m;
int v[N],w[N],dp[N][N];int main() {cin >> n >> m;for (int i = 1;i <= n;i++) {cin >> v[i] >> w[i];}for (int i = 1;i <= n;i++) {for (int j = 1;j <= m;j++) {dp[i][j] = dp[i-1][j];if (j - v[i] >= 0) {dp[i][j] = max(dp[i][j],dp[i-1][j-v[i]] + w[i]);}}}cout << dp[n][m] << endl;return 0;
}

DP优化：

 dp[i][j] = max(dp[i][j],dp[i-1][j-v[i]] + w[i]);转化为dp[j] = max(dp[j],dp[j-v[i]] + w[i]);

if (j - v[i] >= 0) 在j=0时一直为false j可以从v[i]开始，则条件if (j - v[i] >= 0)可以删除

由于j从v[i]开始，从小到大遍历，那么j-v[i]恒小于j,dp[j-v[i]]已经在第i层计算过了

举个例子，我们算i=5时，我们要算dp[5]，可能用到dp[3],dp[4]的值（这里的dp[3],dp[4],是第i=4层的），如果j是从小到大枚举，i=5时，会先算fdp3],dp[4](在第i=5层的值，覆盖掉i=4层的f[3],f[4]值）

所以j应该从m开始,从大到小遍历

优化后的代码如下:

#include <iostream>
#include <algorithm>using namespace std;const int N = 1010;int n , m;
int v[N],w[N],dp[N];int main() {cin >> n >> m;for (int i = 1;i <= n;i++) {cin >> v[i] >> w[i];}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]);}}cout << dp[m] << endl;return 0;
}