2023牛客寒假算法基础集训营4-清楚姐姐学01背包(Easy Version)

Solost

2023 年 01 月 30 日

220 次浏览

暂无评论

1190字数

题目题解

![](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023/01/4234256143.png)

## solution

题目大意，这道题的意思是背包大小是m,有n件物品，最优取的情况下，如果去掉这件物品，能产生的最大价值与不去掉时候的价值差多少。

首先使用01背包把最优情况算出来，然后去掉第i件物品，看看差值。

```C++
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>

for (int i = 1; i <= n; i++) {
        for (int j = m; j >= v[i]; j--) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
  
    for(int k = 1; k <= n; k++){
        ll t = w[k];
        w[k] = 0;
        for(int i = 1; i <= n; i++){
            for(int j = m; j >= v[i]; j--){
                dp[j][k] = max(dp[j][k], dp[j - v[i]][k] + w[i]);
            }
        }
        w[k] = t;
    }
    for(int i = 1; i <= n; i++){
        if(f[m] > dp[m][i]) cout << "0\n";//如果去掉了这件物品，那么他就小于最优情况，他就是必选
        else{//否则输出最优减去不包括第i件物品的时候，记得加1，因为要大于
            cout << f[m] - dp[m - v[i]][i] + 1 - w[i] << endl;
        }
    }
    return 0;
}
```

第二种解法

```cpp
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<fstream>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<unordered_map>

using namespace std;
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e3 + 10;
ll v[N], w[N], f[N];
int n, m;
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 --){
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    ll ans = f[m];//先计算出最优的
    for(int k = 1; k <= n; k++){
        ll t = w[k];
        w[k] = 0;//先把他的价值归零，他肯定不会取
        memset(f, 0, sizeof f);//每次必须初始化，要不然先前的值会更新
        for(int i = 1; i <= n; i++){
            for(int j = m; j >= v[i]; j--){
                f[j] = max(f[j], f[j - v[i]] + w[i]);
            }
        } 
        w[k] = t;//然后把这个值再放回去，等待下一次的
        if(ans > f[m]) cout << "0\n";//如果不取第k件，他比最优小，证明他是必选的
        else{
            cout << ans - f[m - v[k]] + 1 - w[k] << endl;
		//否则最优的减去不包括v[k]时的再减去本身的，因为是大于，再加1
        }
    }
    return 0;
}
```

最后修改：2023 年 02 月 02 日