• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            A Za, A Za, Fighting...

            堅(jiān)信:勤能補(bǔ)拙

            PEARL 硬幣找零(動(dòng)態(tài)規(guī)劃)

            問題描述及代碼:

              1 /*
              2  * Problem:
              3  * given you the coins, and the total amount of money to change, find a solution
              4  * for this change which minimize the number of coins needed.
              5  *
              6  * Example:
              7  * coins[] = {1, 5, 10, 21, 25};
              8  * money = 19;
              9  * solution[] = {10, 5, 1, 1, 1, 1};
             10  *
             11  * Points:
             12  * Dynamic Programming
             13  * Greey Algorithm here is usually uncorrect
             14  */
             15 #include<stdio.h>
             16 #include<stdlib.h>
             17 #include<string.h>
             18 #define MAX_COINS 10
             19 #define MAX_MONEY 32767
             20 #define INF 0x7FFFFFFF
             21 int coins_num, coins[MAX_COINS];
             22 int total, changes_num[MAX_MONEY], changes[MAX_MONEY];
             23 
             24 int
             25 is_continue()
             26 {
             27     char ch[2];
             28     while(1) {
             29         printf("Are you gonna continue this game(Y if yes, or N)?\n");
             30         scanf("%s", ch);
             31         if(ch[0== 'Y' || ch[0== 'y')
             32             return 1;
             33         else if(ch[0== 'N' || ch[0== 'n')
             34             return 0;
             35     }
             36 }
             37 
             38 void
             39 input()
             40 {
             41     int i;
             42     printf("Enter the number of coins: ");
             43     scanf("%d"&coins_num);
             44     printf("Enter the amount of coins(ascending order, separated by space): \n");
             45     for(i=0; i<coins_num; i++)
             46         scanf("%d", coins+i);
             47     printf("Enter the amount of money to change: ");
             48     scanf("%d"&total);
             49 }
             50 
             51 void
             52 output()
             53 {
             54     int i, tmp;
             55     printf("Solution: \n");
             56     printf("Minimum number of coins needed: %d\n", changes_num[total]);
             57     printf("Coins: \n");
             58     tmp = total;
             59     while(tmp > 0) {
             60         printf("%d ", changes[tmp]);
             61         tmp -= changes[tmp];
             62     }
             63     printf("\n");
             64 }
             65 
             66 /*
             67  * Dynamic Programming: f(m) = min (f[m-coins[i] + 1)
             68  * O(N*K), N is the number of coins, K is the total amount of money to change
             69  */
             70 void 
             71 solve()
             72 {
             73     int i, j, k, min;
             74     changes_num[0= 0;
             75     for(i=1; i<=total; i++) { /* Money: from '1' to 'total' */
             76         min = INF;
             77         k = -1;
             78         for(j=0; j<coins_num; j++) { /* Coins: ascending, and always contains '1' */
             79             if(i >= coins[j]) {
             80                 if(min > changes_num[i-coins[j]]+1) {
             81                     min = changes_num[i-coins[j]]+1;
             82                     k = j;
             83                 }
             84             } else
             85                 continue;
             86         }
             87         changes_num[i] = min;
             88         changes[i] = coins[k];
             89     }
             90 }
             91 
             92 int
             93 main(int argc, char **argv)
             94 {
             95     while(is_continue()) {
             96         input();
             97         solve();
             98         output();
             99     }
            100 }

            posted on 2010-09-29 14:18 simplyzhao 閱讀(773) 評(píng)論(0)  編輯 收藏 引用 所屬分類: C_動(dòng)態(tài)規(guī)劃

            導(dǎo)航

            <2010年9月>
            2930311234
            567891011
            12131415161718
            19202122232425
            262728293012
            3456789

            統(tǒng)計(jì)

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            久久国产视频99电影| 精品综合久久久久久98| 亚洲欧美日韩精品久久| 久久久久久国产a免费观看黄色大片| 亚洲精品乱码久久久久66| 国产一区二区三精品久久久无广告| 久久精品国产精品亚洲人人| 一本一本久久aa综合精品 | 久久国产精品成人片免费| 欧美精品一本久久男人的天堂 | 狠狠色丁香久久婷婷综合蜜芽五月| 久久久久久亚洲Av无码精品专口 | 狠狠色丁香久久婷婷综合图片| 精品久久久噜噜噜久久久| 亚洲国产成人久久综合一区77| 久久久亚洲欧洲日产国码二区| 亚洲人成电影网站久久| 99久久国产主播综合精品| 久久久无码人妻精品无码| 无码八A片人妻少妇久久| 久久久久婷婷| 久久国产成人| 久久福利片| 久久久无码精品午夜| 国产日韩久久免费影院| 久久久久免费精品国产| 久久99免费视频| 久久久久久免费一区二区三区| 久久国产精品一国产精品金尊| 久久精品久久久久观看99水蜜桃 | 国产午夜久久影院| 国产精品99久久免费观看| 久久精品夜夜夜夜夜久久| 嫩草伊人久久精品少妇AV| 久久人人爽人人爽人人片av高请 | 蜜桃麻豆www久久| 精品国产VA久久久久久久冰| 亚洲色欲久久久综合网东京热| 亚洲AV无码久久精品狠狠爱浪潮| 久久热这里只有精品在线观看| 久久精品成人欧美大片|