• <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>
            posts - 195,  comments - 30,  trackbacks - 0

            New Zealand currency consists of $100, $50, $20, $10, and $5 notes and $2, $1, 50c, 20c, 10c and 5c coins. Write a program that will determine, for any given amount, in how many ways that amount may be made up. Changing the order of listing does not increase the count. Thus 20c may be made up in 4 ways: 1 20c, 2 10c, 10c+2 5c, and 4 5c.

            Input

            Input will consist of a series of real numbers no greater than $50.00 each on a separate line. Each amount will be valid, that is will be a multiple of 5c. The file will be terminated by a line containing zero (0.00).

            Output

            Output will consist of a line for each of the amounts in the input, each line consisting of the amount of money (with two decimal places and right justified in a field of width 5), followed by the number of ways in which that amount may be made up, right justified in a field of width 12.

            Sample input

             

            0.20
            2.00
            0.00

            Sample output

             

            0.20           4
            2.00         293
            典型的動態規劃問題:
            可以先考慮只有n-1種硬幣,V1,V2,V3,---Vn-1.設湊成總值為M的方法數為result[M];
            現在又添加一種面值為Vn的硬幣。
            則咱們需要修改一些值,修改那些大于等于Vn的result[],不妨設M大于vn。
            新result[M]=原result[M]+result[M-Vn]+result[M-2*Vn]+----直到M-p*Vn<=0;(1)
            實際上如果如(2)那樣處理 從大于等于Vn的result[]開始處理的話,從小到大,設Vn=M-p*Vn;
            則result[M-p*Vn]第一個最先更新,result[M-p*Vn]+=result[M-p*Vn -Vn]   見(2)
            隨后更新result[M-(p-1)*vn],則只需直接加上result[M-p*Vn]的值,無需如(1)式那樣 累加。
            用程序表達就是
            int coin[10]={5,10,20,50,100,200,500,1000,2000,5000};
            for(i=1;i<10;i++)
             for(j=coin[i];j<=50000;j+=5)
                 result[j]+=result[j-Coin[i]];   (2) //
            -------------
            還有一個注意點,見牛人博客,http://hi.baidu.com/piaoshi111/blog/item/9a6de84a00a6e5f882025c89.html
            就是浮點數的四舍五入,
            1.5,浮點數可能表為1.4999999,所以乘以100時轉化為整型是149,應當注意。
            posted on 2009-07-19 21:45 luis 閱讀(479) 評論(0)  編輯 收藏 引用 所屬分類: 動態規劃
            <2011年11月>
            303112345
            6789101112
            13141516171819
            20212223242526
            27282930123
            45678910

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            欧美日韩久久中文字幕| 色综合久久中文字幕综合网| 久久久噜噜噜久久中文字幕色伊伊| 久久久久亚洲国产| 久久精品天天中文字幕人妻 | 青草久久久国产线免观| 久久福利资源国产精品999| 狠狠88综合久久久久综合网| 久久精品无码一区二区三区日韩 | 狠狠干狠狠久久| 日本精品一区二区久久久| 97久久超碰成人精品网站| 日韩va亚洲va欧美va久久| 精品999久久久久久中文字幕| 欧美粉嫩小泬久久久久久久| 97久久精品午夜一区二区| 亚洲国产成人精品女人久久久 | 久久免费视频网站| 伊人久久大香线蕉AV色婷婷色| 国内精品免费久久影院| 久久久久亚洲AV成人片| 蜜桃麻豆WWW久久囤产精品| 久久国产热这里只有精品| 久久久精品人妻一区二区三区四| 伊人伊成久久人综合网777| 国产AV影片久久久久久| 精品免费久久久久久久| 久久99热只有频精品8| 一本色道久久99一综合| 国产精品久久久久久久久久影院| 久久久久免费视频| 久久久久这里只有精品| 99久久人人爽亚洲精品美女| 久久精品国产精品亚洲精品| 久久九九青青国产精品| 国产亚洲精品自在久久| 精品久久无码中文字幕| 潮喷大喷水系列无码久久精品| 久久99热只有频精品8| 久久伊人精品青青草原高清| 91性高湖久久久久|