poj3628-DFS/0-1背包-DP/枚舉-數據比較弱、方法比較多

因為數據范圍20，所以直接枚舉是2^20，不會超時。直接求組合就行。在N個數裡面取1個數，2個數。。。。N個數，求出一個最小差值就可以了。
下面是組合的算法--175MS
[cpp]
#include<stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <math.h> 
 
#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<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
[cpp] 
#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;   
}