C 清楚姐姐学01背包(Easy Version)
思路
求出强制不选择某一物品的最大价值\(v1\)，以及强制选择某一物品的最大价值\(v2\)
- 不选择比选择大说明一定不选 -> 输出\(v1-v2+1\)
- 不选择与选择相等说明可选可不选 -> \(1(v1-v2+1)\)
- 不选择比选择小说明一定选 -> 输出\(0\)
综上， \(max(v1-v2+1,0ll)\)
代码
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
#define X first
#define Y second
typedef pair<int,int> pii;
typedef long long LL;
const char nl = '\n';
const int N = 110;
const int M = 110;
int n,m;
int w[N],v[N];
LL f[N],f2[N];
void solve(){
cin >> n >> m;
int nt = n;
for(int i = 1; i <= n; i ++)cin >> w[i] >> v[i];
for(int k = 1; k <= n; k ++){
memset(f,0,sizeof f); //初始化
for(int i = 1; i <= n; i ++){
if(i == k)continue;
for(int j = m; j >= w[i]; j --){
f[j] = max(f[j],f[j-w[i]]+v[i]);
}
}
LL v1 = f[m]; //不选择
memset(f2,0,sizeof f2); //初始化（不能初始化为v[k]否则会影响后面的dp）
m -= w[k];
for(int i = 1; i <= n; i ++){
if(i == k)continue;
for(int j = m; j >= w[i]; j --){
f2[j] = max(f2[j],f2[j-w[i]]+v[i]);
}
}
LL v2 = f2[m] + v[k]; //选择（后面在加上v[k]）
cout << max(v1-v2+1,0ll) << nl;
m += w[k];
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
solve();
}