Je dois écrire un code avec deux méthodes qui prennent un tableau (non négatif) et une somme de valeurs comme paramètres. Je dois utiliser les méthodes:


public static void printSubsetSums(int[] arr, int sum) {

}

public static void printSubsetSums(int[] arr, int sum, int i, String acc) 
{

}

Nous ne sommes pas autorisés à ajouter des méthodes ou plus de paramètres pour les méthodes actuelles. J'ai fait quelque chose de similaire qui imprime simplement le nombre de sous-ensembles d'un tableau donné en fonction d'une somme. mais j'ai du mal à le changer pour faire cette tâche ... mon tableau est limité à la longueur de 5.

Exemple: Entrée «Entrer 5 nombres dans le tableau»: 1 2 3 4 5 Entrée «Entrer un nombre dans la somme»: 8 3

Pourquoi 3? (3,5), (1,3,4), (1,2,5)

Merci de votre aide!!!

-1
NewToJava 1 juin 2020 à 22:06

3 réponses

Meilleure réponse

L'exigence imposée dans la question est un peu difficile à interpréter. Cependant, j'ai codé pour répondre à votre cas d'utilisation.

L'approche que j'ai utilisée est la suivante:

  1. Trouvez tous les sous-ensembles possibles du tableau donné en utilisant la méthode de manipulation de bits.

  2. Vérifiez si la somme du sous-ensemble est égale à la somme donnée. Si c'est oui, imprimez-le sur la console.

Consultez l'extrait ci-dessous pour plus de clarté.

import java.util.Scanner;

public class SubsetSum {
    public static void printSubsetSums(int[] arr, int sum) {
        printSubsetSums(arr, sum, 0, "NotNeeded");
    }

    public static void printSubsetSums(int[] arr, int sum, int i, String acc) {
        // variable 'i' and 'acc' are not getting used anywhere.
        // Have added because you want to make the same syntax for the function.
        boolean isAnySubsetPossible = false;
        int n = arr.length;

        // Run a loop from 0 to 2^n
        for (int p = 0; p < (1 << n); p++) {
            int[] temporaryArray = new int[n];
            int k = 0;
            int m = 1; // m is used to check set bit in binary representation.
            // Print current subset
            for (int j = 0; j < n; j++) {
                if ((p & m) > 0) {
                    temporaryArray[k++] = arr[j];
                }
                m = m << 1;
            }

            int localSum = 0;
            for (int temp : temporaryArray) {
                localSum += temp;
            }
            if (localSum == sum) { // check if the sum is equal to the desired sum
                isAnySubsetPossible = true;
                for (int item : temporaryArray) {
                    if (item > 0) {
                        System.out.print(item + " ");
                    }
                }
                // print a new line so that next subset starts from new line
                System.out.println();
            }
        }
        if (!isAnySubsetPossible) {
            System.out.println("There is no subset possible for the sum = " + 20);
        }
    }

    public static void main(String[] args) {
        Scanner myScanner = new Scanner(System.in);
        System.out.println("Enter 5 numbers into array");
        int[] myArr = new int[5];
        for (int i = 0; i < myArr.length; i++) {
            myArr[i] = myScanner.nextInt();
        }
        System.out.println("Enter a number into sum");
        int sum = myScanner.nextInt();
        printSubsetSums(myArr, sum);
    }
}

Input1 au programme

Enter 5 numbers into array
1 2 3 4 5
Enter a number into sum
8

Sortie1 par le programme

1 3 4 
1 2 5 
3 5

Input2 au programme

Enter 5 numbers into array
1 2 3 4 5
Enter a number into sum
20

Sortie2 par le programme

There is no subset possible for the sum = 20

J'espère que ça aide.

0
Ajay Kr Choudhary 1 juin 2020 à 20:04

Je pense que vous devez prendre en entrée un tableau de nombres, et donner la somme et le nombre d'entiers qui peuvent être égaux à cette somme

Dans votre exemple:

Entrez 5 nombres dans la matrice: 1 2 3 4 5

Entrez un nombre dans la somme: 8 3 (ici je pense que 3 signifie qu'il ne veut que 3 nombres pour former 8, comme 1 2 5 et 2 3 5 .. etc.)

Vous pouvez le faire de cette manière:

public static void printSubsetSums(int[] arr, int sum, int i) {
    // getting all possible sub arrays of a lentgh of i 
    ArrayList<int[]> subarrays = new ArrayList<int[]>();
    ArrayList<Integer> array = new ArrayList<Integer>();


    int arrSize = arr.length;
    for (int startPoint = 0; startPoint <arrSize ; startPoint++) {
        for (int grps = startPoint; grps <=arrSize ; grps++) {
            for (int j = startPoint ; j < grps ; j++) {
                int element = arr[j];
                array.add(element);
            }
            int[] tab = new int[array.size()];
            int x = 0;
            for(int n : array) {
                tab[x] = n;
                x++;
            }
            subarrays.add(tab);
            array.clear();

        }
    }
    // calculating the sum of each one of these arrays
    // print the ones that their sum equal the sum given with argument
    for(int[] al : subarrays) {
        if (al.length==3) {
            int sum2 = 0;
            for (int n : al) {
                sum2 = sum2 + n;
                System.out.print(n);
            }
            System.out.print(" = "+sum2);
            if(sum2==sum) { System.out.print(" that is a desired sum"); }
            System.out.println();
        }
    }

}
0
Karam Mohamed 1 juin 2020 à 20:03

Voici une approche récursive pour résoudre ce problème:

    public static void printSubsetSums(int[] arr, int sum) {
        printSubsetSums(arr, sum, 0, "");
    }

    public static void printSubsetSums(int[] arr, int sum, int i, String acc) 
    {
        if (sum == 0 && !"".equals(acc)) {
            System.out.println(acc);
            acc = "";
        }
        if (i == arr.length) {
            return;
        }
        printSubsetSums(arr, sum, i + 1, acc);
        printSubsetSums(arr, sum - arr[i], i + 1, acc+" "+arr[i]);
    }

Explication:

Tout d'abord, vous entrez votre tableau d'entiers et la somme souhaitée dans la méthode printSubsetSums(int[] arr, int sum) qui appelle la méthode d'assistance (printSubsetSums(int[] arr, int sum, int i, String acc)), où i est l'index de arr et {{X4 }} est le sortie pour la façon dont la somme a été atteinte.

if (i == arr.length) { return; } agit comme le cas de base pour sortir de la méthode récursive (i est hors limites).

Notez que nous avons deux appels récursifs (printSubsetSums(arr, sum, i + 1, acc) et printSubsetSums(arr, sum - arr[i], i + 1, acc+" "+arr[i])). Le premier agit si le nombre courant ne fonctionne pas pour atteindre la somme et ainsi i est incrémenté pour "réessayer" avec le nombre suivant dans arr. La deuxième option est que le nombre actuel fonctionnera, et donc vous passez à l'index suivant tout en tenant compte du nombre actuel (en le soustrayant de sum pour finalement atteindre 0 [quand nous savons que les nombres sélectionnés ont ajoutez jusqu'à 10] et ajoutez-le à acc).

Enfin, nous imprimons acc lorsque sum vaut 0. Nous définissons également acc = "" et évitons d'imprimer lorsque "".equals(acc) afin d'éviter de compter plusieurs fois la même réponse.

Résultat:

Exemple d'entrée:

printSubsetSums(new int[]{1,2,3,4,5}, 8)

Exemple de sortie:

 3 5
 1 3 4
 1 2 5
0
Armaankoop 2 juin 2020 à 03:15