php implementation Weighing weights (backpack)

1. Summary

One sentence summary:

1. What is the essence of dp?

Brush the table, use space for time

It will be faster if you draw the table

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

2. How to get the initial state of dp (in fact, you can think of it at the beginning is to use the requested state)?

In fact, the first thing you can think of is to use the required state to make the state

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

3. How to obtain the state transition equation of dp?

Try with different initial states

If one dimension does not work, add it to two dimensions, if two dimensions does not work, add it to three dimensions

4. I forgot to initialize the intermediate array here. (between different sets of data)?

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

2. Weighing weights (backpack)

Problem description

There is a set of weights with unequal weights, namely m1, m2, m3...mn;
The corresponding quantities of each weight are x1, x2, x3...xn. Now use these weights to weigh the object and ask how many different weights can be weighed.

Note:

Weighing weight includes 0

Method prototype: public static int fama (int n, int[] weight, int[] nums)

Input description:

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

Output description :

The different weights that can be weighed using the given weight

Example 1

Input

2
1 2
2 1

Output

5

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 ?>

The above is the entire content of this article. I hope it will be helpful to everyone’s study. For more related content, please pay attention to the PHP Chinese website!

Related recommendations:

PHP method to determine whether a link is valid

The basis of PHP implementing AOP

How to generate short connection in php

The above is the detailed content of Introduction to the method of implementing weighing weights in PHP. For more information, please follow other related articles on the PHP Chinese website!