Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.55/11: Рейтинг темы: голосов - 11, средняя оценка - 4.55
0 / 0 / 0
Регистрация: 12.09.2018
Сообщений: 4

Задача на перебор

03.02.2019, 11:50. Показов 2415. Ответов 3

Студворк — интернет-сервис помощи студентам
Нужна помощь в решении, задача:

Вы имеете N камней (1 ≤ N ≤ 10), каждый камень характеризуется весом Pi и стоимостью Vi.
Вы должны сбросить эти камни по желобу в один из двух бункеров: A или B. Механизм
переключения желоба действует следующим образом. Камни падают в один из бункеров,
пока вес содержимого бункера не превысит вес камней в другом бункере не менее, чем на D.
Тогда желоб переключается на другой бункер. В начальный момент оба бункера пусты и
первый камень падает в бункер A. Задача состоит в том, чтобы собрать камни с максимально
возможной стоимостью в бункере B.

Вход
Текстовый файл stones.in состоит из N+1 строк. Первая строка содержит N и D, разделенные
пробелами. Остальные строки содержат величины Pi и Vi, также разделенные пробелами.
Все входные данные, кроме N, целые числа от 0 до 10000

Выход
Текстовый файл stones.out должен содержать одну строку с суммарной стоимостью камней
в бункере B.

Мой код выглядит так:

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
72
#include <fstream>
#include <stdio.h>
#include <iostream>
 
using namespace std ;
 
int v[20][3];
int n, d, a, b;
int in_max;
 
int abs(int a)
{
    if (a < 0 ) return -a;
    else return a;
}
 
void func(int l, int cnt, int sum_a, int sum_b, int value, int arr[])
{   
    if (cnt == 1) 
    {
        sum_b += v[l][0];
        value += v[l][1];
        in_max = max(in_max, value);
    }
    else sum_a += v[l][0];
    
    if (abs(sum_a - sum_b) >= d) cnt = -cnt;
    
    int func_arr[20];
    for (int i=1; i <= n; i++)
        func_arr[i] = arr[i];
    
    for (int i=1; i <= n; i++)
    {
        if ( !func_arr[i] )
        {
            func_arr[i] = 1;
            func(i, cnt, sum_a, sum_b, value, func_arr);
            func_arr[i] = 0;
        }
    }
}
 
int main() 
{ 
    freopen("stones.in", "r", stdin);
    freopen("stones.out", "w", stdout);
    cin >> n >> d;
    for (int i=1; i <= n; i++)
    {
        cin >> a >> b;
        v[i][0] = a;
        v[i][1] = b;
    }
    
    v[0][0]=0;
    v[0][1]=0;
    int arr[20];
    for (int i=1; i <= n; i++)
        arr[i]=0;
    
    
    for (int i=1; i <= n; i++)
    {
        arr[i] = 1;
        func(i, -1, 0, 0, 0, arr);
        arr[i] = 0;
    }   
    
    cout << in_max;
    return 0; 
}
Программа не проходит какой-то из тестов, в чем проблема - идей нет. Подскажите, пожалуйста, где я мог согрешить.
0
Лучшие ответы (1)
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
03.02.2019, 11:50
Ответы с готовыми решениями:

Задача на рекурсивный перебор
В выражении ((((1?2)?3)?4)?5)?6 . Нужно заменить знаки вопроса на знаки +-*/ чтобы в итоге получилось 35. Ну например: 1+2+3*4+5+6=35 ...

Задача дед мороз (перебор)
для начала вот задачка: Подарки Деда Мороза (Время: 1 сек. Память: 16 Мб Сложность: 27%) Ириска весит X грамм, мандарин – Y...

Перебор. Задача про ферзей.
На шахматной доске требуется расставить 8 ферзей, что бы ни один ферзь не атаковал другого. Написал программу. Три дня писал). Что вы...

3
 Аватар для LegionK
393 / 263 / 193
Регистрация: 02.05.2017
Сообщений: 1,003
03.02.2019, 12:24
Лучший ответ Сообщение было отмечено Rodion Ivanov как решение

Решение

Предлагаю решать через перестановки.

Добавлено через 19 минут
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
#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int n,d,m(0);
vector<pair<int,int>>v;
 
bool comp(pair<int,int>f,pair<int,int>s){
    return (f.first > s.first);
}
 
void f(){
    int sum(0),sum1(0),w(0),w1(0);
    bool turn(0);
    for(int i = 0;i<n;++i){
        if(!turn){
            sum += v[i].second;
            w += v[i].first;
        } else {
            sum1 += v[i].second;
            w1 += v[i].first;
        }
        if(abs(w-w1) >= d)turn = 1-turn;
    }
    m = max(m,sum1);
}
 
int main()
{
    cin >> n >> d;
    v.resize(n);
    for(int i = 0;i<n;++i)cin >> v[i].first >> v[i].second;
    sort(v.begin(),v.end());
    f();
    while(next_permutation(v.begin(),v.end(),comp))f();
    cout << m;
    
    return 0;
}
че-то вроде этого
1
0 / 0 / 0
Регистрация: 12.09.2018
Сообщений: 4
03.02.2019, 20:30  [ТС]
Спасибо за ответ. Идея хорошая, объясните только, если не сложно, какой смысл в третьем параметре функции next_permutation?
0
 Аватар для LegionK
393 / 263 / 193
Регистрация: 02.05.2017
Сообщений: 1,003
04.02.2019, 18:00
Rodion Ivanov, это я перестраховался, для типа pair,чтобы сравнивались только первые числа из пары, а то кто его знает что там в стандартном компараторе
Т.е если там vector<int>v то я знаю как стандартная функция сравнения работает - пробовал
А если там vector<pair<int,int>>v я не знаю че он может начать делать - не пробовал
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
04.02.2019, 18:00
Помогаю со студенческими работами здесь

Задача на перебор вариантов. Задача Л.Эйлера. Про чиновника
Задача Л.Эйлера. Некий чиновник купил лошадей и быков на сумму 1770 талеров. За каждую лошадь он уплатил по 31 талеру, а за каждого быка по...

Задача на перебор

Задача на перебор
Среди десяти имеющихся чисел найти пары таких, сумма которых равна 5.

Задача на перебор
Дана задача на перебор: &quot;Дан случайный набор чисел, разбить их на 2 группы минимизировав разницу суммарного веса каждой&quot;. Не совсем...

Задача на перебор
Помогите решить задачу перебором. Задача: Если GREATPEOPLE + ITRANSITION ----------- DEVELOPMENT в позиционной...


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами
8Observer8 20.02.2026
Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
Конвертировать закладки radiotray-ng в m3u-плейлист
damix 19.02.2026
Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru