무게추(배낭)의 PHP 구현

1. 요약

한 문장 요약:

1. dp의 본질은 무엇인가요?

테이블을 닦고 공간을 시간에 활용하세요

테이블을 그리는 것이 더 빠릅니다

13 //动态规划就是一个表
14 //至于这个表的更新就是上面层的表更新下面层的，是逐级更新还是跳级更新要注意
15 //把表画出来做的更快

로그인 후 복사

2. dp의 초기 상태를 얻는 방법(사실 가장 먼저 생각할 수 있는 것은 요청한 상태를 사용하는 것입니다. )?

사실 가장 먼저 생각할 수 있는 것은 필수 상태를 사용하여 상태를 만드는 것입니다

 4 //dp就是思考变量（然后变量组合成初始状态）：变量有用几种砝码，每种砝码有多少个，重量为多少

로그인 후 복사

3. dp의 상태 전이 방정식을 얻는 방법은 무엇입니까?

다른 초기 상태로 시도해 보세요

1차원이 작동하지 않으면 2차원에 추가하고, 2차원이 작동하지 않으면 3차원에 추가하세요

4 중간 배열을 다시 초기화하는 것을 잊었나요? 서로 다른 데이터 집합 사이에서)?

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

로그인 후 복사

2 무게 측정(배낭)

문제 설명

무게가 다른 무게 세트, 즉 m1, m2, m3...mn이 있습니다.
각 무게의 해당 수량은 x1, x2 ,x3입니다. ...xn. 이제 이 무게를 사용하여 물체의 무게를 측정하고 얼마나 많은 무게를 측정할 수 있는지 물어보세요.

참고:

중량 측정에는 0

방법 프로토타입이 포함됩니다. public static int fama(int n, int[] Weight, int[] nums)

In 설명 입력 :

输入包含多组测试数据。
对于每组测试数据：
第一行：n --- 砝码数(范围[1,10])
第二行：m1 m2 m3 ... mn --- 每个砝码的重量(范围[1,2000])
第三行：x1 x2 x3 .... xn --- 每个砝码的数量(范围[1,6])

로그인 후 복사

출력 설명:

주어진 무게를 사용하여 무게를 달 수 있는 다양한 무게의 수

예 1

Input

2
1 2
2 1

로그인 후 복사

Output

로그인 후 복사

Code:

 1 <?php 
 2 //php本身是桶，所以这里用重量来做dp是可以的 
 3 //初始状态  最终状态  状态转移方程 
 4 //dp就是思考变量（然后变量组合成初始状态）：变量有用几种砝码，每种砝码有多少个，重量为多少 
 5 //f[i][j]表示用了第i种砝码用了j个所能达到的重量 
 6 //dp方程为：f[i+1][]=f[i][j]+ 
 7  
 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重量
 12 
 13 //动态规划就是一个表
 14 //至于这个表的更新就是上面层的表更新下面层的，是逐级更新还是跳级更新要注意
 15 //把表画出来做的更快
 16 while($n=trim(fgets(STDIN))){
 17     $w=trim(fgets(STDIN));
 18     $num=trim(fgets(STDIN));
 19     $w=explode(&#39; &#39;,$w);
 20     $num=explode(&#39; &#39;,$num);
 21     $total=10;
 22     for($i=0;$i<$n;$i++){
 23         $total+=$w[$i]*$num[$i];
 24     }
 25 
 26     $dp=null;
 27     $dp[0]=1;
 28     for($i=1;$i<=$n;$i++){
 29         for($j=$total;$j>=0;$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                 } 
35             }
36         }
37     }
38     echo count($dp).PHP_EOL;
39     //print_r($w);
40     //print_r($num);
41 
42 }
43 ?>

로그인 후 복사

이 글의 내용은 여기까지입니다. 모든 분들의 학습에 도움이 되었으면 좋겠습니다. 더 많은 관련 내용을 보시려면 PHP 중국어 홈페이지를 주목해주세요!