刷表啊，用空間換時間

把表畫出來會做得更快

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

其實可以最開始想到的就是用所求做狀態

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

用不同的初始狀態去試

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

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

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

注：

稱重重量包括0

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

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

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

示例1

22 1

5

 1 ?php  2 //php本身是桶，所以這里用重量來做dp是可以的  3 //初始狀態 最終狀態 狀態轉移方程  4 //dp就是思考變量（然后變量組合成初始狀態）：變量有用幾種砝碼，每種砝碼有多少個，重量為多少  5 //f[i][j]表示用了第i種砝碼用了j個所能達到的重量  6 //dp方程為：f[i+1][]=f[i][j]+  8 //f[i][j]表示前i種物品能否達到j重量  9 //f[i][j]=（或者關系）第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 //動態規劃就是一個表 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 ? 

以上就是本文的全部內容，希望對大家的學習有所幫助，更多相關內容請關注PHP ！

相關推薦：

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

PHP實現AOP的基礎

php生成短連接的方法

以上就是php實現稱砝碼的方法介紹的詳細內容，PHP教程

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