Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 28.04.2017, 17:00   #1
MindFure
Новичок
Джуниор
 
Регистрация: 28.04.2017
Сообщений: 1
По умолчанию Вывести числа которые дают в сумме массу рюкзака

Всем привет! написал программу для рюкзака с помощью алгоритма meet in the middle. Он работает нормально, но мне нужно чтоб он выводил числа которые дают сумму рюкзака.

Код:
#include <stdio.h>
#include <list>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
using namespace std;
long long int X[2000005],Y[2000005];
void calsum(long long int a[], long long int x[], int n, int c){
for (int i=0; i<(1<<n); i++){
long long int s = 0;
for (int j=0; j<n; j++)
if (i & (1<<j))
s += a[j+c];
x[i] = s;}}
long long int solveSubsetSum(long long int a[], int n, long long int S){
calsum(a, X, n/2, 0);
calsum(a, Y, n-n/2, n/2);
int size_X = 1<<(n/2);
int size_Y = 1<<(n-n/2);
sort(Y, Y+size_Y);
long long int max = 0;
for (int i=0; i<size_X; i++){
if (X[i] <= S){
int p = lower_bound(Y, Y+size_Y, S-X[i]) - Y;
if (p == size_Y || Y[p] != (S-X[i]))p--;
if ((Y[p]+X[i]) > max)
max = Y[p]+X[i];
}}
return max;}
int main()
{
    long long int a[] = {3, 34, 4, 12, 5, 28};
    int n=sizeof(a)/sizeof(a[0]);
    long long int S = 10;
   cout<<"= %lld\n"<<solveSubsetSum(a,n,S)<<endl;
    return 0;
}
MindFure вне форума Ответить с цитированием
Старый 28.04.2017, 22:42   #2
alexzk
Форумчанин
 
Регистрация: 12.04.2017
Сообщений: 889
По умолчанию

С точки зрения банальной эрудиции каждый здравомыслящий индивидуум не может игнорировать критерии утопичексой субъективности, поэтому цинизм дедов ваших концепций не может ассоциировать с мистикой парадоксальных центрофугических иллюзий.

)
alexzk вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
с++. Даны натуральные числа q1,...,qn. Найти те члены аi последовательности q1,...,qn, которые при делении на 7 дают остаток 1,2 или 5. Nyo Помощь студентам 3 04.09.2016 08:42
Вывести на экран все двухзначные числа которые равны сумме своих цифр и сумме в квадрате/Turbo Pascal Pavel2502 Помощь студентам 5 26.02.2014 22:18
вычислить все числа до n которые равны сумме своих делителей (совершенные числа)//не могу найти ошибку в своей програме на паскале games_vandal Паскаль, Turbo Pascal, PascalABC.NET 0 22.12.2012 14:24
Выведите на экран натуральные числа от 1 до 100, которые при делении на 6 дают в остатке 4 и их количество(цифр) svob Паскаль, Turbo Pascal, PascalABC.NET 9 09.12.2012 20:16
Как удалить строки, которые дают в сумме 0? Demon010 Microsoft Office Excel 12 10.06.2011 13:29