Knapsack 2

chenyiran2012 · 2025-01-16 21:44:49 · 题解

这依旧是一道“典型的dp”
由题意，不难看出这是一道背包dp（01背包）
如往常一样，dp4步走
1：定义状态
以前的dp[i][j]都是表示到第i个物品容量恰好为j的最大总价值是多少，但是这一题中背包容量达到了1e9，数组开不下，怎莫办呢？
很简单，我们只需要把状态稍微一变：dp[i][j]表示到第i个物品总价值恰好为j的最小背包容量，因为用去得背包容量越小，可能装的物品就越多，价值就越大，所以我们要求最小背包容量

2：状态转移方程
以前的01背包都是：dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])(w[i]是体积,v[i]是价值)
而现在是:dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])(w[i]是体积,v[i]是价值)

3: 初始化
因为要求最小值（最小背包容量），所以要赋值极大值 memset(dp,0x3f,sizeof(dp)); 而dp[0][0]=1; (由题意，背包容量最小为1)

4：答案
以前我们应该输出dp[n][m]
现在我们要输出价值 要循环遍历输出（循环价值去找合法的背包容量），找到最大价值输出

注：本人认为用一维数组滚动优化后更简洁
滚动优化（dp数组去掉第1维，只留下第二维，并且第2层循环倒序遍历）

附上代码：

#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
    int sum=0,f=1;
    char ch=getchar();
    while (ch<'0' || ch>'9'){
        if (ch=='-'){
            f=-1;
        }
        ch=getchar();
    }
    while (ch>='0' && ch<='9'){
        sum=sum*10+ch-48;
        ch=getchar();
    }
    return sum*f;
}
void print(int x){
    if (x<0){
        putchar('-');
        x=-x;
    }
    if (x>9){
        print(x/10);
    }
    putchar(x%10+48);
    return;
}
int w[110],v[110];
long long dp[100010];//滚动数组优化 
int main(){
    int n,e;
    cin >> n >> e;//输入 
    int sum=0;
    for (int i=1;i<=n;i++){
        cin >> w[i] >> v[i];//w[i]为体积，v[i]为价值 
        sum+=v[i];//求和 
    }
    memset(dp,0x3f,sizeof(dp));//求最小值赋值最大值 
    dp[0]=0;//初始化 
    for (int i=1;i<=n;i++){//第i个 
        for (int j=sum;j>=v[i];j--){//价值恰好为j （倒序遍历） 
            dp[j]=min(dp[j],dp[j-v[i]]+w[i]);//状态转移方程 
        }
    }
    for (int i=100005;i>=1;i--){//倒序输出（更快） 
        if (dp[i]<=e){//最大价值的合法方案 
            cout << i;//找到就结束 
            return 0;
        }
    }
    return 0;
}

第一次写AtCoder的题解，请多多指教