因为数据范围20，所以直接枚举是2^20，不会超时。直接求组合就行。在N个数里面取1个数，2个数。。。。N个数，求出一个最小差值就可以了。
下面是组合的算法--175MS
[cpp]
#include
#include
#include
#include
#define nMax 25
int N,B;
int height[nMax];
int ans;
int getSum(int pos)
{
int sum = 0;
for (int i = 0; i < N; ++ i )
{
if (pos & (1 << i))
{
sum += height[i];
}
}
return sum;
}
int main()
{
while (scanf("%d %d", &N, &B) != EOF)
{
ans = 0x7FFFFFFF;
for (int i = 0; i < N; ++ i)
{
scanf("%d", &height[i]);
}
for (int i = 1; i < (1 << N) ; ++ i)
{
if (getSum(i) < B)
{
continue;
}
int tmp = getSum(i) - B;
if (ans > tmp)
{
ans = tmp;
}
}
printf("%d\n", ans);
}
return 0;
}
这道题目还可以用01背包动态规划做--32MS
[cpp]
#include
#include
using namespace std;
int f[1000050],c[10000];
int main(){
int n,v;
while(cin>>n>>v){
memset(f,0,sizeof(f));
memset(c,0,sizeof(c));
int sum=0;
for(int i=1;i<=n;++i){
cin>>c[i];
sum+=c[i];
}
for(int i=1;i<=n;i++){
for(int j=sum;j>=c[i];j--)
f[j]=max(f[j],f[j-c[i]]+c[i]);
}
for(int i=1;i<=sum;++i){
if(f[i]>=v){
cout<
}
}
}
return 0;
}
这道题目还可以用dfs深度优先搜索做--32MS
[cpp]
#include
int cow[20];
int b;
int n;
int ans=99999999;
void DFS(int num,int sum)
{
if(sum>=ans) return;
if(num==n)
{
if(sum>=b) ans=sum;
return;
}
DFS(num+1,sum);
DFS(num+1,sum+cow[num]);
}
int main()
{
//freopen("input","r",stdin);
int i,j,cnt,tmp;
int sum;
scanf("%d %d",&n,&b);
for(i=0;i
DFS(0,0);
printf("%d",ans-b);
return 0;
}