


Introduction to the method of implementing weighing weights in PHP
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(' ',$w); 20 $num=explode(' ',$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!

Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Article

Hot Tools

Notepad++7.3.1
Easy-to-use and free code editor

SublimeText3 Chinese version
Chinese version, very easy to use

Zend Studio 13.0.1
Powerful PHP integrated development environment

Dreamweaver CS6
Visual web development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

Hot Topics

Alipay PHP...

JWT is an open standard based on JSON, used to securely transmit information between parties, mainly for identity authentication and information exchange. 1. JWT consists of three parts: Header, Payload and Signature. 2. The working principle of JWT includes three steps: generating JWT, verifying JWT and parsing Payload. 3. When using JWT for authentication in PHP, JWT can be generated and verified, and user role and permission information can be included in advanced usage. 4. Common errors include signature verification failure, token expiration, and payload oversized. Debugging skills include using debugging tools and logging. 5. Performance optimization and best practices include using appropriate signature algorithms, setting validity periods reasonably,

Session hijacking can be achieved through the following steps: 1. Obtain the session ID, 2. Use the session ID, 3. Keep the session active. The methods to prevent session hijacking in PHP include: 1. Use the session_regenerate_id() function to regenerate the session ID, 2. Store session data through the database, 3. Ensure that all session data is transmitted through HTTPS.

The application of SOLID principle in PHP development includes: 1. Single responsibility principle (SRP): Each class is responsible for only one function. 2. Open and close principle (OCP): Changes are achieved through extension rather than modification. 3. Lisch's Substitution Principle (LSP): Subclasses can replace base classes without affecting program accuracy. 4. Interface isolation principle (ISP): Use fine-grained interfaces to avoid dependencies and unused methods. 5. Dependency inversion principle (DIP): High and low-level modules rely on abstraction and are implemented through dependency injection.

How to debug CLI mode in PHPStorm? When developing with PHPStorm, sometimes we need to debug PHP in command line interface (CLI) mode...

Article discusses essential security features in frameworks to protect against vulnerabilities, including input validation, authentication, and regular updates.

How to automatically set the permissions of unixsocket after the system restarts. Every time the system restarts, we need to execute the following command to modify the permissions of unixsocket: sudo...

Static binding (static::) implements late static binding (LSB) in PHP, allowing calling classes to be referenced in static contexts rather than defining classes. 1) The parsing process is performed at runtime, 2) Look up the call class in the inheritance relationship, 3) It may bring performance overhead.
