在一個年終大拍賣活動中,一家迪化街的商店推出了一個特賣活動,
老闆說只要你花錢買 4 個箱子,第一個箱子最多可裝 30 公斤的商品,第二個箱子最多可裝 40 公斤的商品,
第三個箱子最多可裝 50 公斤的商品,第四個箱子最多可裝 25 公斤的商品。
可以挑選的商品有十種,重量分別是 15, 16, 30, 18, 19, 20, 21, 25, 24, 及 17 公斤。
每一種商品最多只能挑一次,且一種商品不可拆開分到不同箱子中。
假設產品加總的重量小於等於箱子的限定重量就一定裝得下這些產品,
由於每樣產品的售價一樣,因此若挑選能裝入 4 個箱子的商品種類愈多,便表示價值愈高。
請你寫一個程式來算出最多可以裝入這些箱子的商品數目,以便估算是否划算。
第一行為兩個整數
其中
第二行開始的
從第
其中
顯示最多能夠裝入這些箱子的商品數目。
若找不到能裝入這些箱子的商品,請輸出 0。
本題保證所有計算過程都不會超出32位元有號整數。
2024/07/24 Update: Added
原TIOJ1719 / TOI2010初選(prob 4)。
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 10 |
2 | 1 | 10 |
3 | 2 | 10 |
4 | 3 | 10 |
5 | 4 | 10 |
6 | 5 | 10 |
7 | 6 | 10 |
8 | 7 | 10 |
9 | 8 | 10 |
10 | 9 | 10 |