Выбор нужных пар целых чисел

@oobarbazanoo · Регистрация: 13.05.2015

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

На вход подаётся число T и какое-то количество пар целых чисел.
Необходимо взять несколько пар так, что бы сумма первых элементов этих пар была не меньше T, а сумма вторых элементов была наименьшей из возможных.
Скорее всего необходимо использовать BST. Подскажите, пожалуйста, как это сделать. Интересут принцип.

@Shamil1 · 01.11.2016, 17:32

Задача о рюкзаке. Только вместо максимума надо искать минимум.

@oobarbazanoo · 01.11.2016, 18:29 **[ТС]**

Трудно понять алгоритм решения. Объясните, пожалуйста, если можете. Как решать мой случай задачи.

Добавлено через 6 минут
Ответ не нужен.

@Shamil1 · 02.11.2016, 11:22

Если сумма всех первых элементов не сильно S отличается о Т, то можно использовать программу для решения задачи о рюкзаке 0-1. Нужно максимизировать цену (второй элемент пары) вещей в рюкзаке вместимостью (S - T). Те вещи, которые не попали в рюкзак, и будут решением.

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

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

F#

let knacksack items t =
    let rec iter (p',ss') ss w p rr =
        match rr with
        | _ when p > p'    -> (p',ss')
        | _ when w >= t    -> (p,ss)
        | []               -> (p',ss')
        | r::rs            ->  let x1 = iter (p',ss') (r::ss) (w + fst r) (p + snd r) rs 
                               let x2 = iter x1 ss w p rs 
                               min x1 x2
    iter (Int32.MaxValue,[]) [] 0 0 (List.sortBy (fun (w,p) -> (double p)/(double w)) items)

(надеюсь, я не ошибся с отсечением)

@oobarbazanoo · 02.11.2016, 14:00 **[ТС]**

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

r::rs

зачем здесь ссылка на метод?

@Shamil1 · 02.11.2016, 15:04

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

зачем здесь ссылка на метод?

Это не ссылка на метод, а сопоставление с образцом.
Список rr можно представить в виде головы r, добавленной в начало хвоста rs.

Добавлено через 40 минут
Переписал, чтобы было понятней

F#

let knacksack items t =
    let rec iter bestItems bestPrice currItems currWeight currPrice restItems =
        match restItems with
        | _ when currPrice > bestPrice    -> (bestPrice, bestItems) // отсекаем ветвь
        | _ when currWeight >= t          -> (currPrice, currItems) // улучшили решение
        | []                              -> (bestPrice, bestItems) // ветвь без решения
        | head::tail                      -> 
            // лучшее решение, содержащее head
            let newItems, newWeight, newPrice = (head::currItems), (currWeight + fst head), (currPrice + snd head)
            let x1 = iter bestItems bestPrice newItems newWeight newPrice tail 
            // лучшее решение, не содержащее head
            let x2 = iter (snd x1) (fst x1) currItems currWeight currPrice tail 
            min x1 x2 
    // сортируем список пар по возрастанию цены за единицу веса, чтобы первое "жадное" решение позволило отсечь больше ветвей
    iter [] (Int32.MaxValue) [] 0 0 (List.sortBy (fun (w,p) -> (double p)/(double w)) items)

Для представления задачи в виде двух подзадач меньшего размера используем факт, что для любого элемента выполняется одно из двух: лучшее решение либо содержит его, либо не содержит его.

Добавлено через 10 минут
исправил опечатку во втором варианте

@oobarbazanoo · 05.11.2016, 21:29 **[ТС]**

Shamil1, извиняюсь, но мне не понятно что Вы написали. Не могли бы Вы это на Java написать, пожалуйста?

@Shamil1 · 05.11.2016, 23:42

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

Не могли бы Вы это на Java написать, пожалуйста?

На java то же самое, только в 5 раз длиннее, так как там нет классов (например, для кортежей), которые в других языках поставляются "из коробки". И ещё, писать все эти классы - нудное занятие.

Добавлено через 36 минут
Вот, например, на C#.

C#

Tuple<int,fnc::List<Tuple<int,int>>> iter(int reqWeight, fnc::List<Tuple<int,int>> bestItems, int bestPrice, fnc::List<Tuple<int,int>> currItems, int currWeight, int currPrice, fnc::List<Tuple<int,int>> restItems)
{
    if(currPrice >= bestPrice) 
        return Tuple.Create(bestPrice, bestItems);
    
    if(currWeight >= reqWeight)
        return Tuple.Create(currPrice, currItems);
 
    if (restItems.IsEmpty)
        return Tuple.Create(bestPrice, bestItems);
        
    var head = restItems.Head;
    var tail = restItems.Tail;
 
    var newItems = currItems.Cons(head);
    var newWeight = currWeight + head.Item1;
    var newPrice = currPrice + head.Item2;
    var x1 = iter (reqWeight, bestItems, bestPrice, newItems, newWeight, newPrice, tail);
 
    var x2 = iter (reqWeight, x1.Item2, x1.Item1, currItems, currWeight, currPrice, tail);
    
    return x1.Item1 < x2.Item1 ? x1 : x2;
}
 
Tuple<int, fnc::List<Tuple<int, int>>> knacksack(fnc::List<Tuple<int, int>> items, int reqWeight)
{
    return iter(reqWeight, fnc::List<Tuple<int, int>>.Empty, Int32.MaxValue, fnc::List<Tuple<int, int>>.Empty, 0, 0,  new fnc::List<Tuple<int, int>>(items.OrderBy(x => (double)x.Item2/x.Item1)) );
}

Неужели так понятней?

з.ы. На java точно так же, то нужно будет самому написать классы для кортежей (Tuple) и односвязного списка (fnc::List).

@oobarbazanoo 7 / 30 / 9 Регистрация: 13.05.2015 Сообщений: 1,835
		1
	Выбор нужных пар целых чисел 01.11.2016, 17:09. Показов 1705. Ответов 7 Метки нет (Все метки) На вход подаётся число T и какое-то количество пар целых чисел. Необходимо взять несколько пар так, что бы сумма первых элементов этих пар была не меньше T, а сумма вторых элементов была наименьшей из возможных. Скорее всего необходимо использовать BST. Подскажите, пожалуйста, как это сделать. Интересут принцип. 0

@Shamil1 Модератор 3051 / 2193 / 459 Регистрация: 26.03.2015 Сообщений: 8,469
	01.11.2016, 17:32	2
	Сообщение было отмечено oobarbazanoo как решение Решение Задача о рюкзаке. Только вместо максимума надо искать минимум. 1

@oobarbazanoo 7 / 30 / 9 Регистрация: 13.05.2015 Сообщений: 1,835
	01.11.2016, 18:29 [ТС]	3
	Трудно понять алгоритм решения. Объясните, пожалуйста, если можете. Как решать мой случай задачи. Добавлено через 6 минут Ответ не нужен. 0

@oobarbazanoo 7 / 30 / 9 Регистрация: 13.05.2015 Сообщений: 1,835
	02.11.2016, 14:00 [ТС]	5
	Сообщение от Shamil1 r::rs зачем здесь ссылка на метод? 0

@oobarbazanoo 7 / 30 / 9 Регистрация: 13.05.2015 Сообщений: 1,835
	05.11.2016, 21:29 [ТС]	7
	Shamil1, извиняюсь, но мне не понятно что Вы написали. Не могли бы Вы это на Java написать, пожалуйста? 0

	05.11.2016, 23:42

Выбор нужных пар целых чисел

Решение