01背包问题(DP)

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

 

原文地址：https://blog.csdn.net/weixin_74749489/article/details/143695677

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！