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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.71
Bek$
1 / 1 / 0
Регистрация: 18.03.2012
Сообщений: 29
#1

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

23.03.2012, 15:13. Просмотров 1885. Ответов 4
Метки нет (Все метки)

Люди помогите, пожалуйста!!! Вот задача (Е-шка). Решал через ДП по профилю, может не то сделал? вот код:

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;
    
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.03.2012, 15:13     Задача о сумме подмножеств
Посмотрите здесь:

Задача о сумме подмножеств - C++
Здравствуйте, прошу помощи. Нужно реализовать алгоритм задачи о сумме подмножеств (subset sum problem) на языке C++. Заранее...

Сколько существует подмножеств данных чисел, дающих в сумме значение меньше z? - C++
помогите решить задачу имеется n различных натуральных чисел. определите, сколько существует подмножеств данных чисел, дающих в сумме...

Задача о сумме - C++
Здравствуйте! мне надо сделать задачу так чтобы было &quot;введите a&quot;, &quot;введите b&quot; и в конце была сумма слагаемых. Я сделал только такую : ...

Задача о сумме подмножества. Псевдокод в код С++ - C++
Доброго времени суток. Пожалуйста, помогите в решении следующей проблемы: необходимо данный псевдокод перевести в исполняемый код С++ (см....

Задача на динамическое программирование(скорее всего) (сколькими способами в сумме получить N, без подряд идущих одинаковых чисел) - C++
Дано число N&lt;106 и три числа A,B,C&lt;=N нужно вывести сколькими способами в сумме получить N, без подряд идущих одинаковых чисел(если N=3,...

Разбиение множества S на M подмножеств - C++
Когда я прописываю числа S и M константами все идеально работает, в противном случае нет. #include &lt;stdio.h&gt; #include &lt;iostream&gt; ...

Алгоритм генерации всех подмножеств с повторениями - C++
Реализовать не рекурсивную версию алгоритма, генерирующего все подмножества с повторениями я правильно понимаю использование подобного...

Генерация всех подмножеств данного множества - C++
Друзья, помогите написать программку в консольном приложении VS 2008, задание такое: Генерация всех подмножеств данного множества Буду...

Перебор всех возможных подмножеств множества целых чисел - C++
Всем привет)))) Пожалуйста, помогите решить задачку!!!!! Очень нужно, срочно!!! Программа перебора всех возможных подмножеств множества...

Перебор всех возможных подмножеств заданного множества целых чисел - C++
Помогите решить задачу. Есть заданное множество целых чисел: -1 0 1. Нужно перебрать все возможные способы размещения в векторе, этих...

Сортировка по сумме цифр - C++
Вывести все элементы массива в порядке неубывания суммы цифр. Я реализовала код, только он сильно большой Как можно его...

Элементы в матрице равны сумме индексов - C++
Доброго времени суток, есть задачка в которой нужно задать матрицу, элементы главной диагонали равны 1, ниже ее -0, а выше равны сумме...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kidasov
77 / 77 / 12
Регистрация: 02.12.2011
Сообщений: 965
Записей в блоге: 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++
4669 / 2495 / 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     Задача о сумме подмножеств
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru