Programmation dynamique LeetCode Day, partie 3

Problème de sac 0-1

Description du sujet

Ming est un scientifique qui doit assister à une importante conférence scientifique internationale pour présenter ses dernières recherches. Il doit apporter du matériel de recherche avec lui, mais il dispose d'un espace limité dans sa valise. Ces matériels de recherche comprennent des équipements expérimentaux, de la littérature, des échantillons expérimentaux, etc., chacun occupant un espace différent et ayant une valeur différente.

L'espace de bagages de Ming est N. Demandez à Ming comment il devrait choisir de transporter les matériaux de recherche ayant la plus grande valeur. Chaque matériau de recherche ne peut être choisi qu'une seule fois, et il n'y a que deux choix : choisir ou ne pas choisir, et aucune découpe ne peut être effectuée.

Description de l'entrée
La première ligne contient deux entiers positifs, le premier entier M représente le type de matériel de recherche et le deuxième entier positif N représente l'espace pour les bagages de Ming.

La deuxième ligne contient M entiers positifs représentant l'espace occupé par chaque type de matériel de recherche.

La troisième ligne contient M entiers positifs représentant la valeur de chaque matériel de recherche.

Description de la sortie
Affichez un nombre entier représentant la valeur maximale des matériaux de recherche que Ming peut transporter.

Exemple de saisie
6 1
2 2 3 1 5 2
2 3 1 5 4 3

Exemple de sortie
5

Conseils
Ming est capable de transporter 6 matériaux de recherche, mais l'espace pour les bagages n'est que de 1, et le matériel de recherche qui occupe 1 espace en vaut 5, donc la réponse finale est la sortie 5.

Plage de données :
1 <= N <= 5000
1 <= M <= 5000
L'espace occupé par les matériaux de recherche et la valeur des matériaux de recherche sont tous deux inférieurs ou égaux à 1000.

public class Main{
    public static void main (String[] args) {
    /* code */
    Scanner s = new Scanner(System.in);

        int M = s.nextInt();
        int N = s.nextInt();
        // clear buffer symbol /n
        s.nextLine();

    String w = s.nextLine();
    String v = s.nextLine();

    int[] weight = Arrays.stream(w.split(" "))
                        .mapToInt(Integer::valueOf)
                        .toArray();
    int[] value = Arrays.stream(v.split(" "))
                        .mapToInt(Integer::valueOf)
                        .toArray();

    int[][] dp = new int[M][N+1];


    for(int i=weight[0]; i<=N; i++){
        dp[0][i] = value[0];
    }

    for(int i=1; i<M; i++){
        for(int j=1; j<=N; j++){
            if(weight[i] > j){
                dp[i][j] = dp[i-1][j];
            }else{
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            }

        }
    }

    System.out.println(dp[M-1][N]);
    }
}




</p>
<p>1, le tableau dp signifie que nous pouvons obtenir la valeur maximale pour l'article i et la taille cible du sac j. La ligne indique l'article et la colonne représente la taille du sac.</p>

<p>2, pour init, on initialise la 1ère ligne et la 1ère col( mais en fait on init le col par défaut 0, ça veut dire)</p>

<p>3, la relation de régression est celle : pour chaque item :<br>
    a, si le poids de l'article est supérieur à la taille du sac, nous ne pouvons pas choisir l'article et la taille actuelle est la taille de la collection des articles précédemment choisis. <br>
    b, si le poids de l'article est ok, nous devons comparer la taille de la collection des articles précédemment choisis moins la taille de l'article actuel (si nous ne le faisons pas, la taille totale sera la taille + la taille de l'élément actuel, cela brisera la logique de notre tableau dp).</p>

<p>Voici l'ordre de la double boucle, car nous pouvons utiliser un tableau 2D pour enregistrer tous les résultats et rechercher la ligne actuelle à partir de la ligne précédente.</p>
<h2>
  
  
  Nous pouvons également utiliser un tableau 1D pour le réaliser.
</h2>



<pre class="brush:php;toolbar:false">    for(int i=1; i<M; i++){
        for(int j=1; j<=N; j++){
            if(weight[i] > j){
                dp[i][j] = dp[i-1][j];
            }else{
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            }

changer pour

        int[] dp = new int[target+1];

        for(int i=1; i<nums.length; i++){
            for(int j=target; j>=1; j--){
                if(nums[i] > j){
                    continue;
                }
                dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);    
            }
        }

---

416. Partitionner la somme des sous-ensembles égaux

Étant donné un tableau entier nums, renvoie vrai si vous pouvez partitionner le tableau en deux sous-ensembles de telle sorte que la somme des éléments des deux sous-ensembles soit égale ou fausse sinon.

Exemple 1 :

Entrée : nums = [1,5,11,5]
Sortie : vrai
Explication : Le tableau peut être partitionné en [1, 5, 5] et [11].
Exemple 2 :

Entrée : nums = [1,2,3,5]
Sortie : faux
Explication : Le tableau ne peut pas être divisé en sous-ensembles à somme égale.

Contraintes :

1 <= nums.length <= 200
1 <= nums[i] <= 100
Page originale

    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if(sum%2==1){
            return false;
        }
        int target = sum>>1;
        int[][] dp = new int[nums.length][target+1];

        for(int i=nums[0]; i<=target; i++){
            dp[0][i] = nums[0];
        }

        for(int i=1; i j){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-nums[i]] + nums[i]);
                }     
            }
        }

        return dp[nums.length-1][target] == target;  
    }





          

            
        
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!