算法1
背包
找最小转换成找最大
然后就是01背包问题
C++ 代码
#include <iostream>
using namespace std;
const int N=33;
const int M=3e5+7;
int n,x;
int w[N];
int f[M];
int sum;
int main() {
cin>>n>>x;
for(int i=1; i<=n; i++) {
cin>>w[i];
sum+=w[i];
}
int m=sum-x;
for(int i=1; i<=n; i++) {
for(int j=m; j>=w[i]; j--) {
f[j]=max(f[j],f[j-w[i]]+w[i]);
}
}
cout<<sum-f[m]<<endl;
return 0;
}
算法2
DFS
选和不选,两种情况,暴搜
C++ 代码
#include <iostream>
using namespace std;
const int N=33;
int res=1e9+7;
int w[N];
int n,x;
int dfs(int u,int sum) {
if(u==n) {
if(sum>=x)res=min(res,sum);
}
else {
dfs(u+1,sum);
dfs(u+1,sum+w[u]);
}
}
int main() {
cin>>n>>x;
for(int i=0; i<n; i++)cin>>w[i];
dfs(0,0);
cout<<res<<endl;
return 0;
}
算法3
bitset
用二进制来存选或者不选得到的所有的价值
C++ 代码
#include <iostream>
#include <bitset>
using namespace std;
const int N = 3e5 + 10;
bitset<N> b;
int n,x;
int main() {
cin>>n>>x;
b[0]=1;
for(int i=1; i<=n; i++) {
int d;
cin>>d;
//选和不选两种情况都可能存在 则把它们的状态作或运算(把可能为1的每一位都保留)
b|=b<<d;
}
//找到第一个比x大的1的位数
while(!b[x++]);
cout<<x-1<<endl;
return 0;
}