poj3628-DFS/0-1背包-DP/枚举-数据比较弱、方法比较多
因为数据范围20，所以直接枚举是2^20，不会超时。直接求组合就行。在N个数里面取1个数，2个数。。。。N个数，求出一个最小差值就可以了。
下面是组合的算法--175MS
#include<stdio.h>#include <stdlib.h>#include <string.h>#include <math.h>#define nMax 25int 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
#include<iostream> #include<cstring> 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<<f[i]-v<<endl; break; } } } return 0; }
这道题目还可以用dfs深度优先搜索做--32MS
#include<stdio.h> 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<n;i++) scanf("%d",&cow[i]); DFS(0,0); printf("%d",ans-b); return 0; }