程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> hdu 1709 The Balance (母函數)

hdu 1709 The Balance (母函數)

編輯:關於C

/*

題目意思: 給你一個n,表示n個物品,下面有n個數,表示n個物品的重量,然後進行稱量,每個物品只有一件,看不能稱出的價值有幾個,輸出它,單獨占一行,

當不為零時,輸出所以不能稱處的價值,並用空格隔開。。。

其中不能稱出的價值包括:除(直接稱出的)和(由直接稱出的得出的差值)的剩余的價值。。ps:有點繞。。。

其實用dp更方便,但為了練習母函數!

*/

[html]  
#include"stdio.h" 
#include"string.h" 
#define MAX  10008 
int main() 

    int a[MAX],c1[MAX],c2[MAX],b[MAX]; 
    int i,j,k,n,sum; 
    while(scanf("%d",&n)!=EOF) 
    { 
        sum=0; 
        for(i=0;i<n;i++) 
        { 
            scanf("%d",&a[i]); 
            sum+=a[i]; 
        } 
        for(i=1;i<=sum;i++) 
        { 
            b[i]=0; 
            c1[i]=c2[i]=0; 
        } 
        for(i=0;i<=1;i++) 
            c1[i*a[0]]=1; 
        for(i=1;i<n;i++) 
        { 
            for(j=0;j<=sum;j++) 
            { 
                for(k=0;k*a[i]+j<=sum&&k<=1;k++) 
                    c2[j+k*a[i]]+=c1[j]; 
            } 
            for(j=0;j<=sum;j++) 
            { 
                c1[j]=c2[j];c2[j]=0; 
            } 
        }//母函數的過程 
        for(i=sum;i>0;i--) 
        { 
            if(c1[i]) 
            { 
                for(j=1;j<i;j++) 
                { 
                    if(c1[j]) 
                        b[i-j]=1; 
                } 
            } 
        }<span style="COLOR: #008000">//</span><span style="COLOR: #008000">這裡是把能有的差值用這種方式找出來</span> 
        k=0; 
        for(i=1;i<=sum;i++) 
        { 
            if(!c1[i]&&!b[i])//將不能稱出的價值存進c2中。。 
                c2[k++]=i; 
        } 
        printf("%d\n",k); 
        if(k) 
        { 
            for(i=0;i<k-1;i++) 
                printf("%d ",c2[i]); 
            printf("%d\n",c2[i]); 
        } 
    } 
    return 0; 


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