Форум программистов, компьютерный форум CyberForum.ru

Задача о сумме подмножеств - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.71
Bek$
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 29
23.03.2012, 15:13     Задача о сумме подмножеств #1
Люди помогите, пожалуйста!!! Вот задача (Е-шка). Решал через ДП по профилю, может не то сделал? вот код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <cstdio>
 
using namespace std;
 
long long a[10];
long long b[10];
long long n,m;
bool f[10][1024];
    
    
bool test(long long profile, long long s)
{
    int sum=0;
    for (int i=0;i<n;i++)
        if (((1 << i) & profile)==(1 << i)) sum+=a[i];
    if (sum==s) return true;
        return false;
}
 
bool go(int i,long long s)
{
    if (i==n)
        {
            if (s==((1<<n)-1)) 
                return true;
            else 
                return false;
        }
    else
        {
            for (int j=0;j<(1<<n);j++)
                if ((f[i][j]==true) && go(i+1,s^j)) return true;
        }
    return false;
}
 
int main()
{
    freopen("ksubset.in","r",stdin);
    freopen("ksubset.out","w",stdout);
    cin>>n>>m;
    long long s=0;
    for (int i=0;i<n;i++)
        {
            cin>>a[i];
            s+=a[i];
            if (a[i]==0) s1++;
        }
    for (int i=0;i<m;i++)
        {
            cin>>b[i];
            s-=b[i];
            if (b[i]==0) s1--;
        }
    if ((s!=0) || (m>n) || (s1<0))
        {
            cout<<"NO"; 
            return 0;
        }
    for (int i=0;i<n;i++)
        {
            for (int j=0;j<(1 << n);j++)
                f[i][j]=test(j,b[i]);
        }
    bool lg=go(0,0);
    if (lg) cout<<"YES";
    else cout<<"NO";
    return 0;
    
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kidasov
76 / 76 / 12
Регистрация: 02.12.2011
Сообщений: 966
Записей в блоге: 3
24.03.2012, 03:20     Задача о сумме подмножеств #2
Код не смотрел, но вот мое решение, если я правильно понял
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <cmath>
using namespace std;
 
bool primeNumber(int a) {
    for (int i = 2; i <= sqrt(a); i++) {
        if(a % i == 0) return false;
    }
    return true;
}
 
int beautNumbers(int a) {
    int Sum = 0;
    int count = 0;
    for (int i = 11;;i++) {
        int j = i;
        while(j) {
            int k = j % 10;
            Sum += k * k;
            j /= 10;
        }
        if (primeNumber(Sum)) count++;
        if (count == a) return i;
        Sum = 0;
    }
}
 
int main()
{
    for (int i = 1; i < 7; i++) cout << beautNumbers(i) << endl;
    return 0;
}
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
24.03.2012, 08:51     Задача о сумме подмножеств #3
Цитата Сообщение от Bek$ Посмотреть сообщение
может не то сделал?
Почему сомневаетесь? Пробовали сдавать задачу и не все тесты проходит?

Вот в этой части использование s1 неправильное:
Цитата Сообщение от Bek$ Посмотреть сообщение
for (int i=0;i<n;i++)
{
cin>>a[i];
s+=a[i];
if (a[i]==0) s1++;
}
for (int i=0;i<m;i++)
{
cin>>b[i];
s-=b[i];
if (b[i]==0) s1--;
}
if ((s!=0) || (m>n) || (s1<0))
{
cout<<"NO";
return 0;
}
Контрпример:
2 1
-50 50
0
Получится s1<0 и Ваш код выдаст "NO", а надо бы "YES"
Bek$
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 29
24.03.2012, 15:54  [ТС]     Задача о сумме подмножеств #4
Kidasov, Vy ne tu zadachu pro4itali))))) Nuzhna E - shka, a A-shka fignya.
valeriikozlov, Spasibo ogromnoe za test popytaus' ispravit'
Женя Т.
 Аватар для Женя Т.
115 / 11 / 1
Регистрация: 02.03.2011
Сообщений: 178
27.03.2015, 16:54     Задача о сумме подмножеств #5
Может кто-то алгоритм подскажет хотя бы ? Эффективный...Чтобы большинство тестов проходило.
До этого воскресенье нужно сдать программу. =\
Yandex
Объявления
27.03.2015, 16:54     Задача о сумме подмножеств
Ответ Создать тему
Опции темы

Текущее время: 07:56. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru