Napisałem kod, aby znaleźć Suma iloczynu wszystkich możliwych podzbiorów macierzy. Otrzymuję oczekiwany wynik, ale nie jestem w stanie zrobić tego wystarczająco szybko, aby usunąć przypadki testowe związane z czasem.Suma iloczynu wszystkich możliwych podzbiorów macierzy
Czy ktoś może mi pomóc w optymalizacji mojego kodu na szybkość?
Pierwsze wejście (testCases) to liczba testcases. W zależności od liczby wersji testowej, będziemy mieć rozmiar tablicy (rozmiar) i elementy tablicy (zestaw).
Na przykład, ważne wejściowy będzie:
1
3
2 3 5
gdzie:
1
oznacza liczbę testami.3
to rozmiar zestawu testowego i2 3 5
są elementami zestawu wejściowego.
oczekiwany wynik wynosi:
71
Obliczenia dla powyższego wyjścia:
{2}, {3}, {5}, {2, 3}, {3, 5}, {2, 5}, {2, 3, 5}
=> 2 3 5 6 15 10 30
=> 2 + 3 + 5 + 6 + 15 + 10 + 30
=> 71
import java.util.Scanner;
public class Test {
static int printSubsets(int set[]) {
int n = set.length;
int b = 0;
for (int i = 0; i < (1 << n); i++) {
int a = 1;
for (int j = 0; j < n; j++){
if ((i & (1 << j)) > 0) {
a *= set[j];
}}
b += a;
}
return b;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int testCases = scanner.nextInt();
for (int i = 0; i < testCases; i++) {
int size = scanner.nextInt();
int set[] = new int[size];
for (int j = 0; j < set.length; j++) {
set[j] = scanner.nextInt();
}
int c = printSubsets(set);
System.out.println((c - 1));
}
scanner.close();
}
}
mógłbyś wyjaśnić swój problem? Jeśli rozumiem cię poprawnie, twój algorytm powinien obliczyć '(2 * 3) + (2 * 5) + (2 * 3 * 5) + (3 * 5) = 61'. – Turing85
Poszczególne elementy są również prawidłowymi podzbiorami. Musisz dodać '2 + 3 + 5' do' 61'. Otrzymujesz '71'. – anacron
Szukasz optymalizacji kodu, który zakładam? "wystarczająco szybki, aby usunąć przypadki testowe związane z czasem". – 7663233