Распределить камни в две кучи так, чтобы модуль разности весов этих двух куч был минимальным

@Diggiti · Регистрация: 03.11.2014

Студворк — интернет-сервис помощи студентам

Доброго времени суток! Требуется программу, которая распределит камни в две кучи так, чтобы модуль разности весов этих двух куч был минимальным. Под весом кучи следует понимать суммарный вес камней в ней. камней от 1 до 100, вес от 1 до 100000. Мне сказали, что эта задача решается с помощью задачи о рюкзаке. Помогите пожалуйста разобраться!

@Diggiti · 14.11.2014, 19:44 **[ТС]**

SlavaSSU, как нибудь попроще))

@SlavaSSU · 14.11.2014, 19:51

Diggiti,

C++ (Qt)
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
#include <iostream>
 
using namespace std;
 
const int INF = (int)(1e9);
 
const int N = 111, MAX = N * 10000;
 
int a[N];
bool good[MAX];
 
int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
 
    int n;
    cin >> n;
 
    int s = 0;
    for(int i = 0; i < n; i++)
        cin >> a[i], s += a[i];
 
    good[0] = true;
 
    for(int i = 0; i < n; i++)
    {
        for(int j = MAX - 1; j >= 0; j--)
        {
            if(good[j])
                good[j + a[i]] = true;
        }
    }
 
    int ans = INF;
 
    for(int i = 0; i < MAX; i++)
    {
        if(good[i])
        {
            if(abs(i - (s - i)) < ans)
                ans = abs(i - (s - i));
        }
    }
 
    cout << ans;
 
    return 0;
}

@Kerry_Jr · 14.11.2014, 19:55

Diggiti,

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
#include <iostream>
#include <cmath>
const int N = 20;
const int max_weight = 100000;
int min = N * max_weight;
int weights[N];
int n;
 
void rec(int k1, int k2, int x)
{
    if (x == n)
    {   
        if (min > abs(k1 - k2)) min = abs(k1 - k2);
    }
    else
    {
        rec(k1, k2+weights[x], x+1);
        rec(k1+weights[x], k2, x+1);
    }
}
 
int main()
{
    std::cin >> n;
    if (n < 1 || n > 20) return 0;
    for (int i = 0; i < n; ++i)
    {
        std::cin >> weights[i];
        if (weights[i] > max_weight) return 0;
    }
    rec(0, 0, 0);
    std::cout << min;
    return 0;
}

@SlavaSSU · 14.11.2014, 19:57

Kerry_Jr, там n до 100 и веса до 10000

@Diggiti · 14.11.2014, 19:58 **[ТС]**

SlavaSSU, Спасибо))) можно с тобой связаться как нибудь? скайп контакт почта))

@Kerry_Jr · 14.11.2014, 20:25

SlavaSSU, просто на тимусе такая же задача есть, перепутал, у них тоже сайт на acm начинается.

@tnk500 · 14.11.2014, 21:20

Можете дать ссылку на задачу?

@ildwine · 14.11.2014, 21:23

Комментарий модератора

Diggiti, вот не надо тут нарушать 4.6

@_Ivana · 14.11.2014, 23:20

Сообщение от SlavaSSU

написать решение проще

Что-то до боли знакомое вспоминается мне при этих словах!

Полагаю, что можно даже написать неприлично простое и настолько же быстрое решение, и возможно, оно даже пройдет все тесты, если повезет

Новые блоги и статьи Все статьи Все блоги /
Remote Connection Manager DevAlt 21.06.2026 Написал для себя небольшую прилагу: https:/ / github. com/ altbodhi/ ReConMan По итогу пришел к мысли, что DU не дружат с существующими технологиями. От сериализации до отображения в реляционную. . .	Администрация Хабра удаляет новые алгоритмы, которые не западно ориентированной философии кода, без уведомлений и объяснений. Hrethgir 20.06.2026 Делается это, как замечено, при правках - при объявлении концептуальных отличий в алгоримах. Делается это, по линейке событий - после дополнения публикации основными отличиями от основных западных. . .	Процесс ориентированная диалектика (не новость - просто системное обновление, философия). Hrethgir 20.06.2026 Однажды один участник в своём блоге, на этом форуме, сделал запись "О языках замолвите слово". Понимая, что язык - важная вещь, я решил хорошо подумать, прежде чем сказать, и сказал то, что вы видите. . .	Контроль уникальности строк в табличной части документа Maks 18.06.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ПланированиеСпецтехники" с табличной частью "НаличиеОборудования", разработанного в КА2. Задача: контроль уникальности строк в. . .
Клиент Uhbif79 18.06.2026 Здесь простой клиент для работы с сервером.	Сервер Uhbif79 18.06.2026 Выкладываю простейший сервер.	Дефенестрация kumehtar 18.06.2026 Узнал интересное слово. Дефенестрация. Это когда ты выбрасываешь кого-либо или что-либо из окна. Возьму на вооружение)))	Дихотомия добра и зла kumehtar 18.06.2026 Как Дзен-буддисты говорят о добре и зле: не нужно воевать против зла, нужно воевать против невежества. Тогда добро станет ествественным, и поэтому вечным. Но дело в том, что невежество всё время. . .

@Diggiti 0 / 0 / 0 Регистрация: 03.11.2014 Сообщений: 16

	Распределить камни в две кучи так, чтобы модуль разности весов этих двух куч был минимальным 14.11.2014, 16:21. Показов 8858. Ответов 28 Метки нет (Все метки) Доброго времени суток! Требуется программу, которая распределит камни в две кучи так, чтобы модуль разности весов этих двух куч был минимальным. Под весом кучи следует понимать суммарный вес камней в ней. камней от 1 до 100, вес от 1 до 100000. Мне сказали, что эта задача решается с помощью задачи о рюкзаке. Помогите пожалуйста разобраться! 0

@Diggiti 0 / 0 / 0 Регистрация: 03.11.2014 Сообщений: 16
	14.11.2014, 19:44 [ТС]
	SlavaSSU, как нибудь попроще)) 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	14.11.2014, 19:57
	Kerry_Jr, там n до 100 и веса до 10000 0

@Diggiti 0 / 0 / 0 Регистрация: 03.11.2014 Сообщений: 16
	14.11.2014, 19:58 [ТС]
	SlavaSSU, Спасибо))) можно с тобой связаться как нибудь? скайп контакт почта)) 0

@Kerry_Jr 3106 / 2591 / 1219 Регистрация: 14.05.2014 Сообщений: 7,236 Записей в блоге: 1
	14.11.2014, 20:25
	SlavaSSU, просто на тимусе такая же задача есть, перепутал, у них тоже сайт на acm начинается. 0

@tnk500 117 / 121 / 42 Регистрация: 25.08.2012 Сообщений: 1,294
	14.11.2014, 21:20
	Можете дать ссылку на задачу? 0