程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj3628-DFS/0-1背包-DP/枚舉-數據比較弱、方法比較多

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

編輯:C++入門知識

因為數據范圍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;   
}   

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved