题目描述
01背包
样例
/*
01背包
选择若干本书,使sum - x最大,sum是书的价值之和
同01背包模板,容量最大是sum - x, 价值是w[i], 容积也是w[i]
f[i][j]即前i本,价值为j的最大值
f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + w[i]);
还可以优化为一维,略过;
*/
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n, x;
const int N = 35, M = 5e5;
int f[N][M], w[N];
int main(){
cin >> n >> x;
int sum = 0;
for(int i = 1; i <= n; i++){
cin >> w[i];
sum += w[i];
}
for(int i = 1; i <= n; i++){
for(int j = 0; j <= sum - x; j++){
f[i][j] = f[i - 1][j];
if(j >= w[i]) f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + w[i]);
}
}
cout << sum - f[n][sum - x];
return 0;
}