先放結論,8張。
先考慮十位,10,20,20,50四張足以表達10,20,……,100十個數,而且無法再減少(窮舉法即可)。
再考慮個位,1,2,2,5四張足夠表達1~10,且無法再減少。
但(1,2,2,5,10,20,20,50)不是這個問題唯一的解,考慮到1+2+2+5=10,則可以將十位數鈔票中的20換成10(注意到把10去掉就不能得到30+),仍然可以得到1~100任意一個數,如果不換,我們也不需要個位數鈔票加和得10,最大隻需要9就可以了,所以可以把一張2換成1(把1去掉就不能得到3)。
於是最少有8張,三個解,分別是:
(1,1,2,5,10,20,20,50)
(1,2,2,5,10,10,20,50)
(1,2,2,5,10,20,20,50)
而第三個解用同樣的鈔票數可以表達1~110任意數值,我認為是最優的。
此外,可以看出想要表達1~K*100間的任意數只需要7+K張rmb即可。
————————-——割———————————
以上是有2元的情況,但是畢竟現在2元不發行了也比較少見,不如考慮沒有2元的情形,這種情形要簡單一些,沒有多解,4元必須用4張1元表示,個位鈔票求和不能到10(不然就要再多一張),所以也不能把20換成10,所以最少需要9張,只有一個解:
(1,1,1,1,5,10,20,20,50)。
先放結論,8張。
先考慮十位,10,20,20,50四張足以表達10,20,……,100十個數,而且無法再減少(窮舉法即可)。
再考慮個位,1,2,2,5四張足夠表達1~10,且無法再減少。
但(1,2,2,5,10,20,20,50)不是這個問題唯一的解,考慮到1+2+2+5=10,則可以將十位數鈔票中的20換成10(注意到把10去掉就不能得到30+),仍然可以得到1~100任意一個數,如果不換,我們也不需要個位數鈔票加和得10,最大隻需要9就可以了,所以可以把一張2換成1(把1去掉就不能得到3)。
於是最少有8張,三個解,分別是:
(1,1,2,5,10,20,20,50)
(1,2,2,5,10,10,20,50)
(1,2,2,5,10,20,20,50)
而第三個解用同樣的鈔票數可以表達1~110任意數值,我認為是最優的。
此外,可以看出想要表達1~K*100間的任意數只需要7+K張rmb即可。
————————-——割———————————
以上是有2元的情況,但是畢竟現在2元不發行了也比較少見,不如考慮沒有2元的情形,這種情形要簡單一些,沒有多解,4元必須用4張1元表示,個位鈔票求和不能到10(不然就要再多一張),所以也不能把20換成10,所以最少需要9張,只有一個解:
(1,1,1,1,5,10,20,20,50)。