suppression d'entiers

Question

Bonjour,
j'ai le programme ci-dessous qui donne les entiers dont la somme est supérieure ou égale à un entier donné. je souhaiterais supprimer le minimum d'entiers dont la somme
est supérieure ou égale à l'entier donné.

merci pour l'aide

import java.util.ArrayList;
import java.util.Arrays;

public class AlgoCombSomComp {
    static void sum_up_recursive(ArrayList<Integer> numbers, int target, ArrayList<Integer> partial) {
       int s = 0;
       for (int x: partial) s += x;
              
       if (s >= target)
        
 System.out.println("sum("+Arrays.toString(partial.toArray())+")="+s + " THE target IS = " +target);
              
       for(int i=0;i<numbers.size();i++) {
             ArrayList<Integer> remaining = new ArrayList<Integer>();
             int n = numbers.get(i);
             
             for (int j=i+1; j<numbers.size();j++) remaining.add(numbers.get(j));
             
             ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial);
             partial_rec.add(n);
                        
             sum_up_recursive(remaining,target,partial_rec);
             
       }
    }
    static void sum_up(ArrayList<Integer> numbers, int target) {
        sum_up_recursive(numbers,target,new ArrayList<Integer>());
    }

    
    public static void main(String args[]) {
        Integer[] numbers = {3,8,9,4,5};
        int target = 18;
        sum_up(new ArrayList<Integer>(Arrays.asList(numbers)),target);
    }
}

Output

sum([3, 8, 9])=20 THE TARGET IS = 18
sum([3, 8, 9, 4])=24 THE TARGET IS = 18
sum([3, 8, 9, 4, 5])=29 THE TARGET IS = 18
sum([3, 8, 9, 5])=25 THE TARGET IS = 18
sum([3, 8, 4, 5])=20 THE TARGET IS = 18
sum([3, 9, 4, 5])=21 THE TARGET IS = 18
sum([8, 9, 4])=21 THE TARGET IS = 18
sum([8, 9, 4, 5])=26 THE TARGET IS = 18
sum([8, 9, 5])=22 THE TARGET IS = 18
sum([9, 4, 5])=18 THE TARGET IS = 18

dans ce cas par exemple, je supprimerai 9, 4, 5 et j'aurai dans {3, 8, 18}

KX · Answer

Bonjour,

Comme je l'ai déjà indiqué dans ta discussion précédente, tu devrais trier tes entiers par ordre croissant.

public static List<Integer> delete(Collection<Integer> numbers, int target) {
    LinkedList<Integer> temp = new LinkedList<>(numbers);
    Collections.sort(temp);
    LinkedList<Integer> result = new LinkedList<>();
    for (int sum = 0, next; sum < target && !temp.isEmpty(); sum += next) {
        next = temp.removeLast();
        result.addFirst(next);
    }
    return result;
}

public static void main(String[] args) {
    List<Integer> result = delete(Arrays.asList(3, 8, 9, 4, 5), 18);
    System.out.println(result); // [5, 8, 9] car 5+8+9=22 > 18
}

Remarque : pour optimiser cette méthode sur un grand nombre de valeurs il faudrait privilégier l'utilisation de Collections.sort avec une ArrayList.

Suppression d'entiers

1 réponse

Discussions similaires

Newsletters