Introduction à la méthode d'implémentation des poids en PHP

Implémentation PHP de poids (sac à dos)

1.Résumé

Résumé en une phrase :

1. Quelle est l'essence de dp ?

Brossez le tableau, utilisez l'espace pour le temps

Ce sera plus rapide si vous dessinez le tableau

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

2. Comment obtenir l'état initial de dp (dans. en fait, cela peut être le meilleur. La première chose qui me vient à l'esprit est d'utiliser l'état souhaité) ?

En fait, la première chose à laquelle vous pouvez penser est d'utiliser l'état requis pour créer l'état

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

3 Comment obtenir l'équation de transition d'état de dp ?

Essayez avec différents états initiaux

Si une dimension ne fonctionne pas, ajoutez-la à deux dimensions, si deux dimensions ne fonctionnent pas, ajoutez-la à trois dimensions

4. J'ai oublié d'initialiser ici encore le tableau intermédiaire (entre différents ensembles de données) ?

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

2. Peser des poids (sac à dos)

Description du problème

Il existe un ensemble de poids avec des poids inégaux, à savoir m1, m2, m3... mn ;
Les quantités correspondantes de chaque poids sont x1, x2, x3...xn. Utilisez maintenant ces poids pour peser l’objet et demandez combien de poids différents peuvent être pesés.

Remarque :

Le poids de pesée comprend 0

Prototype de méthode : public statique int fama (int n, int[] poids, int[] nums)

Description de l'entrée :

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

Description de la sortie :

Le nombre de poids différents pouvant être pesés en utilisant le poids donné

Exemple 1

Entrée

2
1 2
2 1

Sortie

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

Ce qui précède est l'intégralité du contenu de cet article. J'espère qu'il sera utile à l'apprentissage de chacun. Pour un contenu plus connexe. , veuillez faire attention au site Web PHP chinois !

Recommandations associées :

Comment PHP détermine si un lien est valide

La base de PHP pour implémenter AOP

Comment générer un lien court en php

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!