Einführung in die Methode zur Implementierung von Wägegewichten in PHP

PHP-Implementierung von Wiegegewichten (Rucksack)

1. Zusammenfassung in einem Satz:

1.

Bürsten Sie die Tabelle, nutzen Sie den Platz für Zeit

Es geht schneller, wenn Sie die Tabelle zeichnen

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

2. So erhalten Sie den Anfangszustand von dp (tatsächlich, Können Sie sich vorstellen, am Anfang den angeforderten Status zu verwenden)?

Tatsächlich ist das erste, woran Sie denken können, den erforderlichen Zustand zu verwenden, um den Zustand

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

3 zu erhalten. Wie erhält man die Zustandsübergangsgleichung von dp?

Versuchen Sie es mit verschiedenen Anfangszuständen

Wenn eine Dimension nicht funktioniert, fügen Sie sie zu zwei Dimensionen hinzu. Wenn zwei Dimensionen nicht funktionieren, fügen Sie sie zu drei Dimensionen hinzu

4. Ich habe vergessen, das Zwischenarray hier noch einmal zu initialisieren (zwischen verschiedenen Datensätzen)?

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

2. Wiegegewichte (Rucksack)

Problembeschreibung

Es gibt eine Reihe von Gewichten mit ungleichen Gewichten, nämlich m1, m2, m3...mn; 🎜>Die entsprechenden Mengen jedes Gewichts sind x1, x2, x3...xn. Nun wiegen Sie mit diesen Gewichten den Gegenstand und fragen Sie, wie viele verschiedene Gewichte gewogen werden können.

Hinweis:

Das Wiegegewicht umfasst 0

Methodenprototyp:

öffentlich

statisch int fama (int n, int[] Gewicht, int[] Nums)Eingabebeschreibung:

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

Ausgabebeschreibung :

Die verschiedenen Gewichte, die mit dem angegebenen Gewicht gewogen werden können

Beispiel 1

Eingabe

2
1 2
2 1

Ausgabe

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

Das Obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, er wird für das Lernen aller hilfreich sein. Weitere verwandte Inhalte finden Sie auf der chinesischen PHP-Website.

Verwandte Empfehlungen:

Wie PHP bestimmt, ob ein Link gültig ist

Die Grundlage für PHP zur Implementierung von AOP

So generieren Sie einen Kurzlink in PHP

Das obige ist der detaillierte Inhalt vonEinführung in die Methode zur Implementierung von Wägegewichten in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!