刷表啊，用空間換時間

把表畫出來會做得更快

13 //動態(tài)規(guī)劃就是一個表14 //至于這個表的更新就是上面層的表更新下面層的，是逐級更新還是跳級更新要注意15 //把表畫出來做的更快

其實可以最開始想到的就是用所求做狀態(tài)

 4 //dp就是思考變量（然后變量組合成初始狀態(tài)）：變量有用幾種砝碼，每種砝碼有多少個，重量為多少

用不同的初始狀態(tài)去試

一維不行就加到二維，二維不行就加到3維

26 $dp=null;27 $dp[0]=1;

現(xiàn)有一組砝碼，重量互不相等，分別為m1,m2,m3…mn；
每種砝碼對應(yīng)的數(shù)量為x1,x2,x3...xn。現(xiàn)在要用這些砝碼去稱物體的重量，問能稱出多少中不同的重量。

注：

稱重重量包括0

方法原型：html' target='_blank'>public static int fama(int n, int[] weight, int[] nums)

輸入包含多組測試數(shù)據(jù)。對于每組測試數(shù)據(jù)：第一行：n --- 砝碼數(shù)(范圍[1,10])第二行：m1 m2 m3 ... mn --- 每個砝碼的重量(范圍[1,2000])第三行：x1 x2 x3 .... xn --- 每個砝碼的數(shù)量(范圍[1,6])

利用給定的砝碼可以稱出的不同的重量數(shù)

示例1

22 1

5

 1 ?php  2 //php本身是桶，所以這里用重量來做dp是可以的  3 //初始狀態(tài) 最終狀態(tài) 狀態(tài)轉(zhuǎn)移方程  4 //dp就是思考變量（然后變量組合成初始狀態(tài)）：變量有用幾種砝碼，每種砝碼有多少個，重量為多少  5 //f[i][j]表示用了第i種砝碼用了j個所能達到的重量  6 //dp方程為：f[i+1][]=f[i][j]+  8 //f[i][j]表示前i種物品能否達到j(luò)重量  9 //f[i][j]=（或者關(guān)系）第i件物品取0到n(i)件能夠達到 10 //f[i-1][j]||(取)f[i-1][j]+k*wi[k 0- ni] 11 //f[i][j][k]表示前i種物品取j件能否達到k重量 13 //動態(tài)規(guī)劃就是一個表 14 //至于這個表的更新就是上面層的表更新下面層的，是逐級更新還是跳級更新要注意 15 //把表畫出來做的更快 16 while($n=trim(fgets(STDIN))){ 17 $w=trim(fgets(STDIN)); 18 $num=trim(fgets(STDIN)); 19 $w=explode( ,$w); 20 $num=explode( ,$num); 21 $total=10; 22 for($i=0;$i $i++){ 23 $total+=$w[$i]*$num[$i]; 24 } 26 $dp=null; 27 $dp[0]=1; 28 for($i=1;$i $i++){ 29 for($j=$total;$j $j--){ 30 for($k=0;$k =$num[$i-1];$k++){ 31 if($j-$k*$w[$i-1] =0 $dp[$j-$k*$w[$i-1]]){ 32 $dp[$j]=1; 33 break; 34 } 38 echo count($dp).PHP_EOL;39 //print_r($w);40 //print_r($num);43 ? 

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，更多相關(guān)內(nèi)容請關(guān)注PHP ！

相關(guān)推薦：

PHP判斷鏈接是否有效 的方法

PHP實現(xiàn)AOP的基礎(chǔ)

php生成短連接的方法

以上就是php實現(xiàn)稱砝碼的方法介紹的詳細內(nèi)容，PHP教程

鄭重聲明：本文版權(quán)歸原作者所有，轉(zhuǎn)載文章僅為傳播更多信息之目的，如作者信息標記有誤，請第一時間聯(lián)系我們修改或刪除，多謝。