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

Найти максимальный вес картошки, который можно унести в рюкзаке

22.11.2015, 23:56. Показов 6086. Ответов 25
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Найдите максимальный вес картошки, который можно унести в рюкзаке вместительностью s, если есть n картошин с заданными весами.
Входные данные
Первая строка содержит одно число s (1 ≤ s ≤ 10000). Далее следует n (1≤ n ≤ 300) неотрицательных чисел, не превосходящих 100000 - веса картошин.
Выходные данные
Выведите искомый максимальный вес.
Подскажите алгоритм или решение , буду очень благодарен!
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
22.11.2015, 23:56
Ответы с готовыми решениями:

Найдите максимальный вес золота, который можно унести в рюкзаке вместительностью S, если есть N золотых слитко
Найдите максимальный вес золота, который можно унести в рюкзаке вместительностью S, если есть N золотых слитков с заданными весами. ...

Найдите максимальный вес золота, который можно унести в рюкзаке вместительностью S
Помогите решить! А лучше решите за меня=) Найдите максимальный вес золота, который можно унести в рюкзаке вместительностью S, если есть N...

Какую наибольшую массу золота можно унести в таком рюкзаке?
Задача 2 Дано N золотых слитков массой m1, …, mN. Ими наполняют рюкзак, который выдерживает вес не более M. Какую наибольшую массу золота...

25
475 / 427 / 290
Регистрация: 10.03.2015
Сообщений: 1,782
23.11.2015, 00:25
Вывод можно, в принципе, в файл сделать, если необходимо.

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
#include "iostream"
#include "fstream"
 
using namespace std;
 
void main()
{
    int max = 0;
    ifstream fin("file.txt");
    if (!fin.is_open()) cout << "Error.\n";
    else
    {
        int s;
        fin >> s;
        while (!fin.eof())
        {
            int k;
            fin >> k;
            if (k <= s && k > max) max = k;
        }
        cout << "Max = " << max << endl;
        fin.close();
    }
    system("pause");
}
Название: p4E5aT3.png
Просмотров: 251

Размер: 5.4 Кб
0
Dimension
595 / 463 / 223
Регистрация: 08.04.2014
Сообщений: 1,710
23.11.2015, 01:16
Цитата Сообщение от SuperKir Посмотреть сообщение
Вывод можно, в принципе, в файл сделать, если необходимо
зачем ,все равно у вас не правильный код
0
475 / 427 / 290
Регистрация: 10.03.2015
Сообщений: 1,782
23.11.2015, 01:39
Dimension,
Цитата Сообщение от EdHaker Посмотреть сообщение
Найдите максимальный вес картошки, который можно унести в рюкзаке вместительностью s
1
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
23.11.2015, 01:46
Этапять Я еще подумал, как безобразно сформулирована задача - неясно в каких попугаях измеряется "вместимость рюкзака", но SuperKir пошел дальше, и решил задачу буквально как написано - для одной картошки
0
475 / 427 / 290
Регистрация: 10.03.2015
Сообщений: 1,782
23.11.2015, 01:48
_Ivana, О чем и идет речь, как написано, так и делаем
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
23.11.2015, 03:02
Типа такого кота
C++
1
2
3
4
5
6
7
8
9
10
11
int f(int s, int *b, int *e);
 
int l(int s, int *b, int *e, int r) {
    return b>e ? r : l(s,b+1,e, *b<=s ? min(f(s-*b,b+1,e), r) : r);}
 
int f(int s, int *b, int *e) {return l(s,b,e,s);}
 
int main() {
    int s=150, m[]={2,9,130,180,51,135,120,1999,123};
    cout << "Max = " << s-f(s, m, m-1+sizeof(m)/sizeof(m[1]));
}
Он же в лямбдах - часть параметров не надо передавать, т.к. они могут быть захвачены из внешней области видимости, но для рекурсии нужно явно передавать ссылки на лямбды.
C++
1
2
3
4
5
6
7
8
9
10
int main() {
    int s=150, m[]={2,9,130,180,51,135,120,1999,123};
    
    auto f = [&](const auto& lf, int s, int *b, int *e) -> int {
        auto l = [&](const auto& ll, int *b, int r) -> int {
            return b>e ? r : ll(ll, b+1, *b<=s ? min(lf(lf, s-*b, b+1, e), r) : r);};
        return l(l,b,s);};
    
    cout << "Max = " << s-f(f, s, m, m-1+sizeof(m)/sizeof(m[1]));
}
ЗЫ коты представлены в демонстрационных целях - я не рекомендую никому так писать в боевых условиях
0
1 / 1 / 0
Регистрация: 23.09.2015
Сообщений: 101
23.11.2015, 15:05  [ТС]
_Ivana, SuperKir, Dimension, http://www.e-olymp.com/ru/cont... lems/49591 - вот задача, если интересно условие.

Добавлено через 5 часов 14 минут
http://www.e-olymp.com/ru/problems/4831
0
Dimension
595 / 463 / 223
Регистрация: 08.04.2014
Сообщений: 1,710
23.11.2015, 15:21
EdHaker, вот решение ,если не умеете сами искать
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
23.11.2015, 15:26
Dimension, это решение "сложной задачи о рюкзаке", про которую ТС тоже создал тему на форуме, но всем лениво было ему отвечать А в данной теме - простая задача. Мое решение не укладывается в лимит времени только на 2 тестах из 14, остальные проходит. Лень разбираться в чем причина. Может надо предварительно отсортировать картошку и отсекать лишние ветви.
0
Dimension
595 / 463 / 223
Регистрация: 08.04.2014
Сообщений: 1,710
23.11.2015, 15:41
Цитата Сообщение от _Ivana Посмотреть сообщение
это решение "сложной задачи
там разобраны все классические варианты этой задачи
0
23.11.2015, 15:43

Не по теме:

Скорее всего, я взглянул на первые строки и сделал поспешный вывод.

0
1 / 1 / 0
Регистрация: 23.09.2015
Сообщений: 101
23.11.2015, 17:22  [ТС]
_Ivana, подскажите пожалуйста, какой код прошел?
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
23.11.2015, 17:27
С лямбдами не пробовал - не знаю есть ли там С++14. А безлямбдовый вполне прошел.
0
1 / 1 / 0
Регистрация: 23.09.2015
Сообщений: 101
23.11.2015, 17:36  [ТС]
Dimension, и где там решение? я читал эту статью, там нет такой же задачи

Добавлено через 22 секунды
_Ivana, как переделать под динамический массив? у вас же установлена длинна( можете кинуть код?
0
Dimension
595 / 463 / 223
Регистрация: 08.04.2014
Сообщений: 1,710
23.11.2015, 17:50
EdHaker, внимательнее читайте
0
1 / 1 / 0
Регистрация: 23.09.2015
Сообщений: 101
23.11.2015, 18:25  [ТС]
Dimension, так там не хватает в программе данных, до какого кол-ва мне считывать, я не могу понять никак, у меня же не вводится сколько будет кол-ва слитков!!!

Добавлено через 10 минут
_Ivana, можете показать код, который прошел или как реализовать эту работу с массивом?(

Добавлено через 11 минут
ну пождскажите вы, вот код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
int main(){
int n=0,sum=0;
int m[300],p[300];
cin>>n;
for ( int i=0;i<3;i++)
cin>>m[i];
 
 
sort(m, m +3);
for (int i=0;i<3;i++)   {       
      if (n >= m[i])    
       {sum += p[i];}
else {sum += n / m[i] * p[i];
      break;}
       n -= m[i]; }
 
cout<<sum<<endl;
return 0;
}
Добавлено через 11 секунд
Что в нем не так?
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
23.11.2015, 19:45
После простой оптимизации все равно на одном тесте не укладывается в лимит времени. Мемоизация нужна наверное.

EdHaker, я уже показал двух котов - достаточно.
0
1 / 1 / 0
Регистрация: 23.09.2015
Сообщений: 101
23.11.2015, 22:07  [ТС]
_Ivana, не работает ваш код, как вы сделали динамику?
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
23.11.2015, 22:21
Работает. Но вы не можете даже запустить готовый. А динамики я никакой не знаю и не умею - поэтому пользуюсь статикой и не жужжу
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
23.11.2015, 22:21
Помогаю со студенческими работами здесь

Распределить вес предметов, которые могут унести мальчики и девочки
Получается нужно от общего веса предметов отнимать массив весов. Как только мальчик не может нести вещь больше N-кол-ва кг, то мы нагружаем...

Найти максимальный по площади выпуклый четырехугольник, который можно организовать из точек на плоскости
В двухмерном пространстве задается некоторое количество точек . Нужно найти максимальный по площади выпуклый четырехугольник, которых из...

Определить вес почтового груза который можно поместить в самолет
Помогите пожалуууууйста с программой на c++ Пассажирский самолет может поднять груз общим весом 30т. Составить программу для определения...

Определить вес почтового груза, который можно поместить в самолет, после посадки N пассажиров
пассажирский самолет может поднять груз общим весом R кг. составить программу определения веса почтового груза, который можно поместит в...

Найти максимальный рост и минимальный вес
Помогите пожалуйста. Создать два массива(вес и рост) и найти максимальный рост и минимальный вес и их порядковый номер.


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
Модель заражения группы наркоманов
alhaos 17.04.2026
Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .
Мысли в слух. Про "навсегда".
kumehtar 16.04.2026
Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .
My Business CRM
MaGz GoLd 16.04.2026
Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .
Знаешь почему 90% людей редко бывают счастливыми?
kumehtar 14.04.2026
Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.
Фиксация колонок в отчете СКД
Maks 14.04.2026
Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .
Настройки VS Code
Loafer 13.04.2026
{ "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .
Оптимизация кода на разграничение прав доступа к элементам формы
Maks 13.04.2026
Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений
Maks 12.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru