Купить больше половины карандашей, но при этом потратив минимум денег

@Arman132 · Регистрация: 28.02.2021

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

Условно говоря есть упаковки карандашей, в i-ой упаковке a(i) карандашей, стоимость упаковки b(i), то есть есть список [[a1,b1],[a2,b2],[a3,b3],[a4,b4]...]. Нужно купить больше половины карандашей, но при этом потратив минимум денег. Пока решение в голову не приходит. Кто-то может подсказать?

Новичок · 07.03.2021, 21:49

Сортировка по a_i / b_i ?

@Arman132 · 07.03.2021, 23:06 **[ТС]**

Сообщение от Новичок

Сортировка по ai / bi ?

.
Если я правильно понял о чем вы, то для теста [[10,7],[20,20],[31,26]] прога даст ответ 27 за 30 карандашей, хотя выгоднее купить 31 карандаш за 26

Новичок · 08.03.2021, 02:28

Да, действительно, только там даже более неоптимальный ответ выйдет. А какие ограничения на кол-во упаковок ? Есть простое решение с перебором, но это очень неэффективно.

@Arman132 · 08.03.2021, 10:51 **[ТС]**

Сообщение от Новичок

А какие ограничения на кол-во упаковок ?

в сумме упаковок не больше 2017

@avgoor · 08.03.2021, 11:15

Arman132, это задача о рюкзаке почти в чистом виде.

@Arman132 · 08.03.2021, 11:19 **[ТС]**

avgoor, спасибо

IGPIGP · 08.03.2021, 11:28

Arman132, я бы предложил сортировать по стоимости за штуку. Для того чтобы с плавающей точкой не связываться (а может и зря, учитывая современные матпроцессороы) настрогал компоратор)

C++

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
 
struct rate_ineger_comparator
{
    bool operator()(const pair<int,int> &left, const pair<int,int> &right)
    {
        //можете убрать локальные переменные, которые умный компиллер и сам уберёт
        //для порядку)
        int rate_left=left.second/left.first;
        int rate_right=right.second/right.first ;
        if(rate_left<rate_right) return true;
        if(rate_left>rate_right) return false;
        //равны
        int rem_left=left.second%left.first ;
        int rem_right=right.second%right.first ;
        if (rem_left<rem_right) return true;
        return false;
    }
};
 
int main()
{
    vector<pair<int,int>> pens
    {
    {20,20}
    ,{10,7}
    ,{31,26}
    };
sort(pens.begin(), pens.end(), rate_ineger_comparator{});
for(auto el:pens)cout<<el.first<<' '<<el.second<<endl;
 
return 0;
}

Однако алгоритм набора стоимости чуть кучеряв и если праздник позволит, я ещё появлюсь. Но надеюсь вы сами его найдёте.
Желаю милым дамам хороших поздравителей с букетами, а хорошим поздравителям букеты милых дам.

@avgoor · 08.03.2021, 12:20

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

Однако алгоритм набора стоимости чуть кучеряв и если праздник позволит, я ещё появлюсь.

С мегабакса от института Клея проставитесь?

IGPIGP · 08.03.2021, 12:21

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

С мегабакса от института Клея проставитесь?

Расскажите подробнее. Если берёте на себя организацию - ваша половина.

@avgoor · 08.03.2021, 12:33

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

Расскажите подробнее.

Если вы сможете решить задачу ТС-а за полиномиальное время, то...
Задача эквивалентна следующей:
Владелец лавки собирает самые ценные наборы в свой рюкзак (вместимостью N/2-1, где N - общее число карандашей) и убегает в закат. Тем самым вы докажете равенство P и NP классов, что является задачей тысячелетия.

Добавлено через 1 минуту

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

ваша половина.

Заметано

IGPIGP · 08.03.2021, 12:35

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

Заметано

Возможно мне решение просто кажется несложным. Но... Миллион это не так уж и много, чтобы пожертвовать таким праздником. Посмотрим к вечеру и/или завтра.

@avgoor · 08.03.2021, 12:44

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

Но... Миллион это не так уж и много, чтобы пожертвовать таким праздником. Посмотрим к вечеру и/или завтра.

Мы с женой уже употребляем.

IGPIGP · 08.03.2021, 13:12

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

Мы с женой уже употребляем.

Поутру - классика жанра

Солнце нынче встало,
Осветить бокалы.

IGPIGP Комп_Оратор) $Эксперт по математике/физике$ 8950 / 4704 / 629 Регистрация: 04.12.2011 Сообщений: 13,999 Записей в блоге: 16
	08.03.2021, 13:12	14
	Сообщение от avgoor Мы с женой уже употребляем. Поутру - классика жанра Солнце нынче встало, Осветить бокалы. 0

@Arman132 0 / 0 / 0 Регистрация: 28.02.2021 Сообщений: 10
		1
	Купить больше половины карандашей, но при этом потратив минимум денег 07.03.2021, 17:52. Показов 1463. Ответов 13 Метки нет (Все метки) Условно говоря есть упаковки карандашей, в i-ой упаковке a(i) карандашей, стоимость упаковки b(i), то есть есть список [[a1,b1],[a2,b2],[a3,b3],[a4,b4]...]. Нужно купить больше половины карандашей, но при этом потратив минимум денег. Пока решение в голову не приходит. Кто-то может подсказать? 0

Новичок 1642 / 1091 / 487 Регистрация: 17.07.2012 Сообщений: 5,345
	07.03.2021, 21:49	2
	Сортировка по a_i / b_i ? 0

@Arman132 0 / 0 / 0 Регистрация: 28.02.2021 Сообщений: 10
	07.03.2021, 23:06 [ТС]	3
	Сообщение от Новичок Сортировка по ai / bi ? . Если я правильно понял о чем вы, то для теста [[10,7],[20,20],[31,26]] прога даст ответ 27 за 30 карандашей, хотя выгоднее купить 31 карандаш за 26 0

Новичок 1642 / 1091 / 487 Регистрация: 17.07.2012 Сообщений: 5,345
	08.03.2021, 02:28	4
	Да, действительно, только там даже более неоптимальный ответ выйдет. А какие ограничения на кол-во упаковок ? Есть простое решение с перебором, но это очень неэффективно. 0

@Arman132 0 / 0 / 0 Регистрация: 28.02.2021 Сообщений: 10
	08.03.2021, 10:51 [ТС]	5
	Сообщение от Новичок А какие ограничения на кол-во упаковок ? в сумме упаковок не больше 2017 0

@avgoor 1550 / 875 / 179 Регистрация: 05.12.2015 Сообщений: 2,555
	08.03.2021, 11:15	6
	Сообщение было отмечено Arman132 как решение Решение Arman132, это задача о рюкзаке почти в чистом виде. 1

@Arman132 0 / 0 / 0 Регистрация: 28.02.2021 Сообщений: 10
	08.03.2021, 11:19 [ТС]	7
	avgoor, спасибо 0

@avgoor 1550 / 875 / 179 Регистрация: 05.12.2015 Сообщений: 2,555
	08.03.2021, 12:20	9
	Сообщение от IGPIGP Однако алгоритм набора стоимости чуть кучеряв и если праздник позволит, я ещё появлюсь. С мегабакса от института Клея проставитесь? 0

IGPIGP Комп_Оратор) $Эксперт по математике/физике$ 8950 / 4704 / 629 Регистрация: 04.12.2011 Сообщений: 13,999 Записей в блоге: 16
	08.03.2021, 12:21	10
	Сообщение от avgoor С мегабакса от института Клея проставитесь? Расскажите подробнее. Если берёте на себя организацию - ваша половина. 0

@avgoor 1550 / 875 / 179 Регистрация: 05.12.2015 Сообщений: 2,555
	08.03.2021, 12:33	11
	Сообщение от IGPIGP Расскажите подробнее. Если вы сможете решить задачу ТС-а за полиномиальное время, то... Задача эквивалентна следующей: Владелец лавки собирает самые ценные наборы в свой рюкзак (вместимостью N/2-1, где N - общее число карандашей) и убегает в закат. Тем самым вы докажете равенство P и NP классов, что является задачей тысячелетия. Добавлено через 1 минуту Сообщение от IGPIGP ваша половина. Заметано 1

IGPIGP Комп_Оратор) $Эксперт по математике/физике$ 8950 / 4704 / 629 Регистрация: 04.12.2011 Сообщений: 13,999 Записей в блоге: 16
	08.03.2021, 12:35	12
	Сообщение от avgoor Заметано Возможно мне решение просто кажется несложным. Но... Миллион это не так уж и много, чтобы пожертвовать таким праздником. Посмотрим к вечеру и/или завтра. 0

@avgoor 1550 / 875 / 179 Регистрация: 05.12.2015 Сообщений: 2,555
	08.03.2021, 12:44	13
	Сообщение от IGPIGP Но... Миллион это не так уж и много, чтобы пожертвовать таким праздником. Посмотрим к вечеру и/или завтра. Мы с женой уже употребляем. 0

Купить больше половины карандашей, но при этом потратив минимум денег

Решение