题解 | #【模板】01背包#

每个物品只有放入、不放入两种情况，而且每个物品只能取一次，取背包的最大价值例题:

• P1048 [NOIP2005 普及组] 采药
• P1734 最大约数和
• P1060 [NOIP2006 普及组] 开心的金明

二维数组模版

    int n, m; cin >> n >> m;
    // w[i] 第i个物品的重量
    // v[i] 第i个物品的价值
    for(int i = 1; i <= n; i ++)
        cin >> w[i] >> v[i];

    // dp[i][j] 前i个物品放入容量为j的背包的最大价值
    // 当前背包容量是j,要考虑当前物品能否放入?是否放入?
    // 1. 如果当前背包容量是j < w[i],放不下，则dp[i][j] = dp[i - 1][j]
    // 2 如果当前背包容量能放得下
    // 2.1 放入后的背包价值 dp[i - 1][j - w[i]] + v[i]
    // 2.1 不放入 dp[i - 1][j]

    // 01背包模版
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            dp[i][j] = dp[i - 1][j];
            if(w[i] <= j){
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
            }
        }
    }
    // 结果
    cout << dp[n][m] << endl;

一维滚动数组优化

我们可知dp[i][j]是由dp[i-1][...]推到而来的，在二维数组中，只需要进入前一行即i-1行的记录就好了，因此我们可以使用一维滚动数组来优化二维数组，但是注意要逆序！（因为我们需要从旧的结果推进得到新的值，如果正序，则当前的值可能是由本行数据递推而来的，并不是前一行推进来的，，导致同一件物品多次取的情况，所以我们要逆序，从而保证f[j - w[i]]是前一行的值）一维数组,逆序循环(避免一件物品重复取)

//一维优化
for(int i=1;i<=n;i++){
	// 优化: j < v[i]时无法放入，依旧保持原始的值即可
	for(int j=m;j>=v[i];j--){
		dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
	}
} 

背包装满时的最大价值

前提是必须背包装满时的最大价值，装不满不算。此时我们只需要修改初始状态即可:

1. 初始化dp[0]=0
2. 其余dp[j] = -INF (最小值) 如果有物品能恰好装满容量为j的背包，那么一定是由dp[0]转移过来的，否则dp[j]是-INF，即无法转移而来 最后判断dp[m]是否是-INF，既可以判断背包是否可以被填满

   // 是否装满
   // 初始化 dp[0] = 0, 其余的都是 dp[i] = -INF最小值
   // 因此所有的状态dp[i] 都是由 dp[0] 转移过去的
   dp[0] = 0; // 表示装满容量为0的背包时的体积
   for(int i = 1; i <= m; i ++) dp[i] = -INF;

   // 开始dp
   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]);
       }
   }

   if(dp[m] < 0){
       // 意味着不能装满
       dp[m] = 0;
   }
   cout << dp[m];

AC代码

二维数组

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
const int INF = 0x3f3f3f3f;
int v[N]; // 体积 volume
int w[N]; // 价值 worth
int dp[N][N];
int main() {
    int n, m;
    cin >> n  >> m;

    for (int i = 1; i <= n; i ++) {
        cin >> v[i] >> w[i];
    }

    // 01背包
    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j <= m; j ++) {
            dp[i][j] = dp[i - 1][j];
            // 是否放得下
            if (j >= v[i]) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
            }
        }
    }

    cout << dp[n][m] << endl;

    for (int i = 0; i <= n; i ++)
        for (int j = 0; j <= m; j ++)
            dp[i][j] = -INF;

    dp[0][0] = 0;
    // 开始dp
    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j <= m; j ++) {
            dp[i][j] = dp[i - 1][j];
            // 是否放得下
            if (j >= v[i]) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
            }
        }
    }

    if (dp[n][m] < 0) {
        // 意味着不能装满
        dp[n][m] = 0;
    }
    cout << dp[n][m];
    return 0;
}

一维数组

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
const int INF = 0x3f3f3f3f;
int v[N]; // 体积 volume
int w[N]; // 价值 worth
int dp[N];
int main(){
    int n, m;  cin >> n  >> m;

    for(int i = 1; i <= n; i ++){
        cin >> v[i] >> w[i];
    }

    // 01背包
    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;

    // 是否装满
    // 初始化 dp[0] = 0, 其余的都是 dp[i] = -INF最小值
    // 因此所有的状态dp[i] 都是由 dp[0] 转移过去的
    dp[0] = 0; // 表示装满容量为0的背包时的体积
    for(int i = 1; i <= m; i ++) dp[i] = -INF;

    // 开始dp
    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]);
        }
    }

    if(dp[m] < 0){
        // 意味着不能装满
        dp[m] = 0;
    }
    cout << dp[m];
    return 0;
}