Podział zbioru Cpp pomocy

Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
Ola00
Rozkręcam się
Rozkręcam się
Posty: 48
Rejestracja: 30 lis 2021, 14:55
Podziękowania: 12 razy

Podział zbioru Cpp pomocy

Post autor: Ola00 » 11 sty 2023, 23:54

4. PODZIAŁ ZBIORU
Parametry: Skończony zbiór \(C=\{c_1,\ldots,c_q\}\) oraz waga \(s(c_i)\) związana z każdym elementem \(c_i\in C\).
Pytanie: Czy istnieje podzbiór \(C'\subset C\) taki, że \(\sum\limits_{c_i\in C'}s(c_i)=\sum\limits_{c_i\in C- C'}s(c_i)\)? Jeśli tak, to podać ten podział.


Witam, jestem początkująca potrzebowałam pomocy z zadaniu z podziałem zbioru ma on losował randomowo elementy i wagi oraz wynik nie jest poprawny.

Kod: Zaznacz cały

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    setlocale(LC_ALL, "");
     
    vector<int> C;
     
    vector<int> s;
     
    vector<int> C_sub;
     
    int sum_C = 0;
     
    int sum_C_sub = 0;
 
     
    int q;
    cout << "Podaj liczbe elementow: ";
    cin >> q;
 
    cout << "Podaj elementy zbioru C i wagi: " << endl;
    for (int i = 0; i < q; i++) {
        int c;
        int weight;
        cin >> c >> weight;
        C.push_back(c);
        s.push_back(weight);
        sum_C += weight;
    }
 
     
    int i = 0;
    while (sum_C_sub <= sum_C / 2 && i < q) {
        sum_C_sub += s[i];
        C_sub.push_back(C[i]);
        i++;
    }
 
     
    if (sum_C_sub == sum_C - sum_C_sub) {
        cout << "Istnieje taki podzbior że C` zawiera sie C taki, że suma po ci nalezy do C` od s(ci) = suma po ci nalezy do C - C` od s(ci)." << endl;
        cout << "Podzbior C` to: ";
        for (int element : C_sub) {
            cout << element << " ";
        }
        cout << endl;
    }
    else {
        cout << "Nie istnieje podzbior taki że C` zawiera się C taki, że suma po ci należy do C` od s(ci) = suma po ci nalezy do C - C` od s(ci)." << endl;
    }
 
    return 0;
}
Ostatnio zmieniony 12 sty 2023, 12:13 przez Jerry, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości; przepisałem złącznik. Przeczytaj, proszę, jeszcze raz reguły tworzenia wątków/postów

Awatar użytkownika
szw1710
Fachowiec
Fachowiec
Posty: 966
Rejestracja: 04 sty 2020, 13:47
Lokalizacja: Cieszyn
Podziękowania: 9 razy
Otrzymane podziękowania: 360 razy
Płeć:

Re: Podział zbioru Cpp pomocy

Post autor: szw1710 » 12 sty 2023, 13:44

Taki podzbiór nie zawsze istnieje. Niech wszystkie wagi będą równe 1, \(C=\{1,2,3\}\). Nie jestem informatykiem, ale metoda brute force mogłaby polegać na generowaniu wszystkich podzbiorów i liczeniu sum wag elementów zbioru i jego dopełnienia. Algorytm kończy się albo po znalezieniu podziału, albo po wyznaczeniu wszystkich możliwych podziałów. Tak więc potrzeba znać algorytm generowania wszystkich podzbiorów danego zbioru, a do tego potrzeba algorytmu generowania wszystkich podzbiorów o zadanej liczbie elementów.

Tu masz wygooglowaną odpowiedź na pytanie o taki algorytm.

https://stackoverflow.com/questions/108 ... single-set

A tu szersze omówienie tego algorytmu:

https://compprog.wordpress.com/2007/10/ ... g-subsets/

Nic tylko sprawdzić czy działa i dopisać sprawdzanie sum wag.
Oglądaj moją playlistę Matura rozgrzewka.