問(wèn)題描述：用隨意多個(gè)1 2 5三個(gè)數(shù)字的組合，使其值為100，有多少種組合方法？

基礎(chǔ)解法：窮舉法，1窮舉100次，2窮舉50次，5窮舉20次，這種方法總共窮舉的次數(shù)為100*50*20=100 000，性能太差，但是為了以后描述問(wèn)題，先給出窮舉法的代碼：

?

for(int i = 0; i <= 100; i += 5){for(int j = 0; j <= 100; j += 2){for(int k = 0; k <= 100; k++)if(i + j + k == 100)count++;} }

?

?進(jìn)階解法：通過(guò)對(duì)窮舉法進(jìn)行考察，在窮舉的過(guò)程中j并不是每次都循環(huán)50次，而是隨著i的增加循環(huán)次數(shù)不斷減小，可以動(dòng)態(tài)計(jì)算其循環(huán)次數(shù)為(100 - i) / 2，對(duì)于1的循環(huán)次數(shù)為可以動(dòng)態(tài)計(jì)算為(100 - i - j)，通過(guò)這個(gè)描述可以得到一個(gè)新的解法。

?

for(int i = 0; i <= 100; i += 5){for(int j = 0; j <= 100 - i; j += 2){for(int k = 0; k <= 100 - i - j; k++)if(i + j + k == 100)count++;} }

?

?進(jìn)一步優(yōu)化：通過(guò)對(duì)上述算法的進(jìn)一步分析，其實(shí)對(duì)1沒有必要循環(huán)，只要i+j <= 100肯定存在一種解法，也就是說(shuō)1肯定能補(bǔ)全差值。因此對(duì)1的循環(huán)是沒有必要的。

?

for(int i = 0; i <= 100; i += 5){for(int j = 0; j <= 100 - i; j += 2){count++; }

?

最優(yōu)解法：通過(guò)對(duì)上述優(yōu)化再進(jìn)一步分析，對(duì)于2，是否有必要循環(huán)呢？其實(shí)我們只要知道100 - i對(duì)于2的倍數(shù)就行了，小于這個(gè)倍數(shù)100 - i - j可以用1來(lái)補(bǔ)全。因此可以有(100 - i) / 2種組合。考慮到i的個(gè)數(shù)可以為0，因此應(yīng)該用這個(gè)倍數(shù)加1。因此我們只需要20次循環(huán)就可以找到總的倍數(shù)了。算法如下：

?

?

for(int i = 0; i <= 100; i += 5){count += (100 - i + 2) / 2; //其也可以寫成count += ((100 - i) / 2 + 1) }

?

其實(shí)通過(guò)這個(gè)小的編程題的一步步優(yōu)化，我們已經(jīng)在使用動(dòng)態(tài)規(guī)劃的思想了，其思想的核心就是剪去一些不必要的計(jì)算，在進(jìn)階解法中，我剪掉了不必要的循環(huán)次數(shù)，在進(jìn)一步優(yōu)化中我們剪掉了1的循環(huán)，最優(yōu)解法中我們將對(duì)2的循環(huán)也剪掉了，形成了最好的解決辦法。

總結(jié)

以上是生活随笔為你收集整理的1 2 5组合100，有多少种方法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。