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

poj 1742 Coins (背包)

編輯:關於C

題目大意:給出n種面值的硬幣, 和這些硬幣每一種的數量, 要求求出能組成的錢數(小於等於m)

Ps:用多重背包的方法做在poj上超時了(hdoj行), 然後在網上看到一個方法, 用f[j]表示能組成這價值為j的錢和不能(0與1), 用used[j]表示當前這種面值為j時用了A[i]多少次。
code:
#include <stdio.h> 
#include <string.h> 
int main() 

    int i = 0, j = 0, n = 0, m = 0, ans = 0, A[102], C[102], f[100002], used[100002]; 
    while(scanf("%d %d",&n, &m) , n+m) 
    { 
        memset(f, 0, sizeof(f)); 
        for(i = 0; i<n; i++) 
            scanf("%d",&A[i]); 
        for(i = 0; i<n; i++) 
            scanf("%d",&C[i]); 
        f[0] = 1; 
        for(i = 0; i<n; i++) 
        { 
            for(j = 0; j<=m; j++)//全部初始化, 表示當前面值為j時用了A[i]0次 
                used[j] = 0; 
            for(j = A[i]; j<=m; j++) 
            { 
                if(!f[j] && f[j-A[i]] && used[j-A[i]]<C[i])//f[j]為1時used[j]=0 
 
                { 
                    f[j] = 1; 
                    used[j] = used[j-A[i]]+1; 
                } 
            } 
        } 
        ans = 0; 
        for(i = 1; i<=m; i++) 
            if(f[i]) 
                ans++; 
        printf("%d\n",ans); 
    } 
    return 0; 


多重背包
code:
#include <stdio.h> 
#include <string.h> 
int n = 0, m = 0, A[102], C[102], dp[100002]; 
void zero_one(int weight, int value) 

    int j = 0; 
    for(j = m; j>=weight; j--) 
        dp[j] = dp[j]>dp[j-weight]+value? dp[j]:dp[j-weight]+value; 

int main() 

    int i = 0, j = 0, k = 0, sum = 0, ans = 0; 
    while(scanf("%d %d",&n, &m), n+m) 
    { 
        memset(dp, 0, sizeof(dp)); 
        ans = 0; 
        for(i = 0; i<n; i++) 
            scanf("%d",&A[i]); 
        for(i = 0; i<n; i++) 
            scanf("%d",&C[i]); 
        for(i = 0; i<n; i++) 
        { 
            sum = A[i]*C[i]; 
            if(sum>m)//完全背包 
                for(j = A[i]; j<=m; j++) 
                    dp[j] = dp[j]>dp[j-A[i]]+A[i]? dp[j]:dp[j-A[i]]+A[i]; 
            else 
            { 
                k = 1; 
                while(k<C[i])//2進制拆分 
                { 
                    zero_one(k*A[i], k*A[i]); 
                    C[i] -= k; 
                    k *= 2; 
                } 
                zero_one(C[i]*A[i], C[i]*A[i]); 
            } 
        } 
        for(i = 1; i<=m; i++) 
            if(dp[i] == i) 
                ans++; 
        printf("%d\n",ans); 
    } 
    return 0; www.2cto.com


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