• <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...

            堅信:勤能補拙

            PEARL 硬幣找零(動態規劃)

            問題描述及代碼:

              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) 評論(0)  編輯 收藏 引用 所屬分類: C_動態規劃

            導航

            <2010年7月>
            27282930123
            45678910
            11121314151617
            18192021222324
            25262728293031
            1234567

            統計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            蜜臀久久99精品久久久久久小说 | 中文字幕精品无码久久久久久3D日动漫 | 99国产精品久久| 97久久精品人人澡人人爽| 久久久精品人妻无码专区不卡| 久久中文精品无码中文字幕| 久久久精品国产亚洲成人满18免费网站 | 久久综合狠狠综合久久| 日本免费久久久久久久网站| 久久九九久精品国产| 久久综合综合久久综合| 久久久久久青草大香综合精品| 久久久精品人妻一区二区三区蜜桃| 国产成人无码久久久精品一| 污污内射久久一区二区欧美日韩 | 精品综合久久久久久97| 国产精品成人久久久久三级午夜电影| 四虎国产精品成人免费久久| 久久精品人人做人人爽电影蜜月| 香蕉99久久国产综合精品宅男自| 国产精品久久久久久吹潮| 中文字幕无码久久人妻| 国产精品无码久久四虎| 久久99精品久久久久久久久久| 少妇久久久久久被弄到高潮| 777久久精品一区二区三区无码| 久久久精品2019免费观看| 99蜜桃臀久久久欧美精品网站| 国产成人综合久久久久久| 伊人久久免费视频| 91精品国产色综久久| 精品国际久久久久999波多野| 亚洲精品高清国产一线久久| 国产A级毛片久久久精品毛片| 久久久久久久免费视频| 少妇人妻综合久久中文字幕| 久久综合久久伊人| 日韩影院久久| 少妇精品久久久一区二区三区| 7777精品伊人久久久大香线蕉| 久久久精品久久久久影院|