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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 33, средняя оценка - 4.76
tpoiiia
0 / 0 / 0
Регистрация: 20.04.2012
Сообщений: 3
#1

Разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной. - C++

22.04.2012, 10:38. Просмотров 4866. Ответов 16
Метки нет (Все метки)

Здравствуйте, помогите, пожалуйста, решить данную ниже задачу.

У Вас есть N камней с массами W1, W2 , … WN. Требуется разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной.
Входные данные

В первой строке входного файла INPUT.TXT записано число N – количество камней (1 ≤ N ≤ 18). Во второй строке через пробел перечислены массы камней W1, W2 , … WN (1 ≤ Wi ≤ 105).
Выходные данные

В единственную строку выходного файла OUTPUT.TXT нужно вывести одно неотрицательное целое число – минимально возможную разницу между массами двух кучек.
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.04.2012, 10:38
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной. (C++):

Распределить камни в две кучи так, чтобы разность весов этих двух куч была минимальной - C++
Ограничение времени: 1.0 секунды Ограничение памяти: 64 МБ У вас есть несколько камней известного веса w1, …, wn. Напишите...

Распределить камни в две кучи так, чтобы модуль разности весов этих двух куч был минимальным - C++
Доброго времени суток! Требуется программу, которая распределит камни в две кучи так, чтобы модуль разности весов этих двух куч был...

Распределить числа в два массива так, чтобы разность между их суммами была минимальной - C++
Задача: дан массив N чисел. Нужно раскидать эти числа в два массива так, чтобы разность между их суммами была минимальной. Пример: 100 1...

Разложить число в массив так, чтобы элементами была последовательность с единицы о этого числа - C++
как разложить число и записать в массив....например дано 4 4= 4 3 2 1 в масив записать 4 3 2 1

В матрице выбрать n элементов в разных строках и разных столбцах так, чтобы их сумма была минимальной - C++
Помогите,пожалуйста Добавлено через 2 часа 23 минуты примерный алгоритм как это можно сделать

Модернизируйте функцию factorial так, чтобы она не была рекурсивной - C++
Пример программы: // Вычисляющей сумму, разность и факториал // двух чисел #include <iostream.h> class MyInt { int i; ...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 1
22.04.2012, 12:11 #2
примени динамическое программирование. главное полный перебор не делай - он не оптимален.
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.04.2012, 12:26 #3
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
главное полный перебор не делай - он не оптимален.
В данном случае это не правда. При таких ограничениях:
Цитата Сообщение от tpoiiia Посмотреть сообщение
N – количество камней (1 ≤ N ≤ 18).
полный перебор займет меньше секунды.
1
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 1
22.04.2012, 13:14 #4
тебе при полном переборе предстоит перебрать 2^18 вариантов
или 262144, для каждого найти вес И того
262144*18=4718592 действий это минимум
если на нахождение одного варианта у тебя одна операция тратится
пять миллионов меньше чем за секунду?

Добавлено через 16 минут
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
int solve(int* a, int N){
int s=0;
int i;
for (i=0; i<N; i++)
 s+=a[i];
int* t1, t2, t3;
int sz=s/2+s%2;
int* t1=new int[sz+1];
int* t2=new int[sz+1];
for (i=0; i<sz; i++)
{
    t1[sz]=0; t2[sz]=0;
}
for (i=0; i<N; i++){
 for (j=0; j<=sz; j++){
    if (j-a[i]>=0){
         t2[j]=max(t1[j], t1[j-a[i]]+a[i]);
       }
       else
         t2[j]=t1[j];
  }
t3=t2;
t2=t1;
t1=t3;
}
delete[] t1;
delete[] t2;
 
 
int a, dsz, c;
a=s-t2[sz];
if (a>t2[sz]) dsz=a-t2[sz];
else dsz=t2[sz]-a;
a=s-t2[sz-1];
if (a>t2[sz-1]) c=a-t2[sz];
else c=t2[sz]-a;
 
if (dsz<c) return dsz;
else return c 
}
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.04.2012, 13:35 #5
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
тебе при полном переборе предстоит перебрать 2^18 вариантов
или 262144, для каждого найти вес И того
262144*18=4718592 действий это минимум
если на нахождение одного варианта у тебя одна операция тратится
пять миллионов меньше чем за секунду?
Kuzia domovenok, у Вас очень плохо с математикой. Вот код:
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
#include <stdio.h>
#include <math.h>
int res, N, mas[18];
void rec(int n, int sum1, int sum2)
{
    if(n==N)
    {
        if(abs(sum1-sum2)<res)
            res=abs(sum1-sum2);
        return;
    }
    rec(n+1, sum1+mas[n], sum2);
    rec(n+1, sum1, sum2+mas[n]);
}
int main()
{
      freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
    res=2000000;
    int i;
    scanf("%d", &N);
    for(i=0; i<N; i++)
        scanf("%d", &mas[i]);
    rec(0,0,0);
    printf("%d\n", res);
 
return 0;
}
в котором реализован полный перебор. Всего действий (+ или -) в нем 2^18=262144 вариантов. Еще столько же вариантов (если често то в два раза больше, но можно написать код чтобы было столько же) - это сравнение полученного результата с имеющимся. Ни о каких
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
4718592 действий
речь не идет.
Чтобы не быть голословным я нашел эту задачу. Она здесь:
http://********/?main=task&id_task=71
Мой код прошел все тесты и показал: 0,197 секунды.
Итог: все-таки с математикой Вы не сильно дружите ).
4
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 1
22.04.2012, 13:47 #6
ну вот, я тебе и написал 262144, прочесть не смог?
рекурсия запросто увеличит это число в несколько раз

У тебя алгоритм экспоненциальной сложности,
а у меня порядка N*N*Wсред
Максимум 34000 действий, и то, если все без исключения камни по 108 весят
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.04.2012, 14:04 #7
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
ну вот, я тебе и написал 262144, прочесть не смог?
смог, но еще смог прочитать:
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
262144*18=4718592 действий это минимум
если на нахождение одного варианта у тебя одна операция тратится
пять миллионов меньше чем за секунду?
Насчет ДП против ничего не имею, кстати первый раз сдавал эту задачу именно с помощью ДП. Но в данном случае опровергаю выдвинную Вами "теорию":
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
главное полный перебор не делай - он не оптимален.

Не по теме:

А Вы сами пробовали Ваш код сдавать по указанной ссылке?

0
tpoiiia
0 / 0 / 0
Регистрация: 20.04.2012
Сообщений: 3
22.04.2012, 14:34  [ТС] #8
valeriikozlov, спасибо большое за код.
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 1
22.04.2012, 14:41 #9
Цитата Сообщение от valeriikozlov Посмотреть сообщение
А Вы сами пробовали Ваш код сдавать по указанной ссылке?
смотрел ссылку, ничего не понял. Это какой-то задачник по программированию?
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.04.2012, 14:51 #10
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
смотрел ссылку, ничего не понял. Это какой-то задачник по программированию?
Это система онлайн проверки решений олимпиадных задач. Если есть желание, то начинайте отсюда:
http://********/
здесь регистрируйтесь и обязательно прочитайте раздел "новичкам".
2
thick_int
Заблокирован
22.04.2012, 15:51 #11
А что делать будете, если камней будет не 18, а скажем 10000?
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.04.2012, 20:25 #12
Цитата Сообщение от thick_int Посмотреть сообщение
А что делать будете, если камней будет не 18, а скажем 10000?
Решать.

thick_int, Вы просто теорию хотите узнать или есть задача, на эту же тему, только с ограничениями N до 10000? Если есть такая задача, то давайте ссылку на нее.
0
thick_int
Заблокирован
23.04.2012, 03:14 #13
Ну вообще-то про теорию решения подобных задач.
Мне вот так кажется, что исходная задача сводится к задаче нахождения кортежа, такого что, разница между суммой элементов которого и половиной суммарной массы, минимальна.
0
djkah11
0 / 0 / 0
Регистрация: 03.07.2012
Сообщений: 5
03.07.2012, 00:12 #14
Решал задачу сам, вот сделал такое решение.
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
#include <iostream>
 
 
using namespace std;
 
int main()
{
int a,t;
cin>>a;
int b[19];
for (int i=0;i<a;i++) {cin>>b[i];}
if (a!=1) {
for (int y=0;y<a;y++){
    for (int h=y+1;h<a;h++) {
        if (b[y]>b[h])
         {t=b[y];
         b[y]=b[h];
         b[h]=t;
         }
         }
         }
 
 int s1=b[a-1];
 
 int s2=b[a-2];
  
 int k=a-3;
 
  while (k>(-1)) {
        if (s1>s2) { s2+=b[k];} else {s1+=b[k];}
        
        k--;
}
 
int u=s1-s2;
if (u>0) {cout<<u;} else {cout<<-u;};}
 
      else {cout<<b[0];};
         
 
 
 
 
    return 0;
}
Подскажите плз в чем ошибка, вроде сам тестил - все работает.
P.s. решал задачу с другим условием у меня кол-во камней от 1 до 20.
0
neske
1495 / 862 / 82
Регистрация: 26.03.2010
Сообщений: 2,951
03.07.2012, 00:21 #15
напишите алгоритм для дп пожалуйста)
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.07.2012, 00:21
Привет! Вот еще темы с ответами:

Переставить буквы в строке так, чтобы первой буквой была гласная - C++
Есть строка &quot;acomabugopabt&quot; Сколько есть различных способов переставить буквы в этой строке так, чтобы первой буквой была...

Как объявить переменную так, чтобы она была видна в .h файле? - C++
День всем добрый! Допустим, есть у меня код в главном .cpp файле: #include &quot;Windows.h&quot; #include &quot;my.h&quot; using namespace...

рабочая программа. но нужно ее переписать так, чтобы она была наиболее общей. - C++
Задана матрица смежности размерности N*M. С помощью процедуры и матрицы меньшей размерности найти медианы и записать в виде матрицы...

Как обратиться к объекту bitset так, чтобы результатом была битовая маска - C++
Здравствуйте, для образовательных целей решил научится работать с bitset, как я понял класс эмулирует массив с размером элемента 1 бит....


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
03.07.2012, 00:21
Ответ Создать тему
Опции темы

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