作者stallings ()
看板Grad-ProbAsk
標題[理工] 111 中興資工數學
時間Thu Feb 24 10:48:12 2022
有 1 元、2 元、5 元鈔票，都至少有 5 張
任意取 5 張，可有幾種不同的總額？
小的不才，請問這題怎麼做？謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.217.58.181 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1645670894.A.2B0.html
1F：推 bnn1999: 暴力解吧02/24 10:49
2F：→ bnn1999: 最低就5，最高就2502/24 10:50
3F：→ stallings: 我也只會列表然後算個數 XD02/24 10:54
4F：→ stallings: 所以想問一下比較好的做法02/24 10:54
5F：→ chang1248w: generating function 代102/24 11:06
6F：→ chang1248w: +1+x...x^a)(1+x^2+x^4...x^2b)(1+x^5...x^5c)02/24 11:10
7F：→ chang1248w: 不對，不是代1，是看有幾項不同的02/24 11:10
8F：推 joywilliamjo: 生成函數下去看有幾個不同的x次方，取5到25次的就好02/24 15:21
9F：→ joywilliamjo: 了02/24 15:21
把 (0 1 2 3 4 5)(0 2 4 6 8 10)(0 5 10 15 20 25) 勇敢乘開
發現 x^5 ~ x^25 的係數都不為 0，感覺怪怪的
這才想起，這個式子只表現出 a, b, c >= 0，
卻沒有使用到 a + b + c = 5 這個條件啊 = =
請問要如何克服？Orz
※ 編輯: stallings (180.217.58.181 臺灣), 02/24/2022 17:06:57
10F：推 jacksoncsie: 我覺得 brute force 02/24 17:14
11F：推 joywilliamjo: 對欸，但數字不大，暴力很快 02/24 17:25
12F：→ chang1248w: 就看x^5的係數啊 02/24 20:10
13F：推 mpyh12345: 我進考場腦袋空空 還好不大直接硬幹 02/25 02:29
14F：推 GTR12534: 最多 21 種，稍微配配看吧，是我也硬爆 03/01 18:44
15F：→ GTR12534: 不然就是先看組合再看金額 03/01 18:45
16F：→ GTR12534: 500/410/320/311/221 03/01 18:47
17F：→ katian: 最快就暴力吧 可以先把所有面額減1不影響答案 變成1元和4 03/08 10:13
18F：→ katian: 元最多5張 1元取4張以上沒有意義 4元取最多2張時1元都能 03/08 10:13
19F：→ katian: 取 之後遞減 總共4*3+3+2+1=18 03/08 10:13
20F：→ stallings: 還有這種操作 = = 我有空來想想看 謝謝 03/08 13:10
21F：推 elfkiller2: 應該就是面額減1的思路暴力解最快 不過少加一個全0 04/08 13:13
22F：→ elfkiller2: 可湊出0~17跟20 共19種 04/08 13:14
23F：推 elfkiller2: 15也湊不出來 應該是18種沒錯 04/08 13:23
24F：推 Lustar: H 3 取 5 01/30 17:26