Рубрики

Дробный рюкзак

Учитывая вес и значения n предметов, нам нужно положить эти предметы в рюкзак вместимостью W, чтобы получить максимальную общую стоимость в рюкзаке.

В задаче о ранце 0-1 нам не разрешается разбивать предметы. Мы либо берем весь товар, либо не берем его.

Input:
  Items as (value, weight) pairs
  arr[] = {{60, 10}, {100, 20}, {120, 30}}
  Knapsack Capacity, W = 50;
Output:
  Maximum possible value = 220
  by taking items of weight 20 and 30 kg 

В Fractional Knapsack мы можем разбить предметы для максимизации общей стоимости рюкзака. Эта проблема, в которой мы можем сломать предмет, также называется проблемой дробного ранца.

Input : 
   Same as above
Output :
   Maximum possible value = 240
   By taking full items of 10 kg, 20 kg and 
   2/3rd of last item of 30 kg

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

Эффективным решением является использование жадного подхода. Основная идея жадного подхода состоит в том, чтобы рассчитать соотношение / вес для каждого предмета и отсортировать предмет на основе этого соотношения. Затем возьмите элемент с наибольшим соотношением и добавляйте его до тех пор, пока мы не сможем добавить следующий элемент целиком, а в конце добавьте следующий элемент как можно больше. Который всегда будет оптимальным решением этой проблемы.

Простой код с нашей собственной функцией сравнения может быть написан следующим образом. Пожалуйста, смотрите функцию сортировки более подробно. Третий аргумент функции сортировки — это наша функция сравнения, которая сортирует элемент в соответствии с отношением цена / вес в неубывающем порядке.
После сортировки нам нужно перебрать эти предметы и добавить их в наш рюкзак, удовлетворяющий вышеупомянутым критериям.

C ++

// C / C ++ программа для решения дробной задачи о ранце
#include <bits/stdc++.h>

  

using namespace std;

  
// Структура для элемента, который хранит вес и соответствующий
// значение Item

struct Item

{

    int value, weight;

  

    // Конструктор

    Item(int value, int weight) : value(value), weight(weight)

    {}

};

  
// Функция сравнения для сортировки товара по соотношению вес / вес

bool cmp(struct Item a, struct Item b)

{

    double r1 = (double)a.value / a.weight;

    double r2 = (double)b.value / b.weight;

    return r1 > r2;

}

  
// Основная жадная функция для решения проблемы

double fractionalKnapsack(int W, struct Item arr[], int n)

{

    // сортировка товара по соотношению

    sort(arr, arr + n, cmp);

  

    // Раскомментируем, чтобы увидеть новый порядок товаров с их соотношением

    / *

    для (int i = 0; i <n; i ++)

    {

        cout << arr [i] .value << "" << arr [i] .weight << ":"

             << ((double) arr [i] .value / arr [i] .weight) << endl;

    }

    * /

  

    int curWeight = 0;  // Текущий вес в рюкзаке

    double finalvalue = 0.0; // Результат (значение в рюкзаке)

  

    // цикл по всем пунктам

    for (int i = 0; i < n; i++)

    {

        // Если добавление элемента не будет переполнено, добавьте его полностью

        if (curWeight + arr[i].weight <= W)

        {

            curWeight += arr[i].weight;

            finalvalue += arr[i].value;

        }

  

        // Если мы не можем добавить текущий элемент, добавляем его дробную часть

        else

        {

            int remain = W - curWeight;

            finalvalue += arr[i].value * ((double) remain / arr[i].weight);

            break;

        }

    }

  

    // Возвращаем финальное значение

    return finalvalue;

}

  
// программа драйвера для проверки вышеуказанной функции

int main()

{

    int W = 50;   // Вес рюкзака

    Item arr[] = {{60, 10}, {100, 20}, {120, 30}};

  

    int n = sizeof(arr) / sizeof(arr[0]);

  

    cout << "Maximum value we can obtain = "

         << fractionalKnapsack(W, arr, n);

    return 0;

}

Джава

// Java-программа для решения дробной задачи о ранце

import java.util.Arrays;

import java.util.Comparator;

  
// Жадный подход

public class FractionalKnapSack

{

    // Временная сложность O (n log n)

    public static void main(String[] args)

    {

        int[] wt = {10, 40, 20, 30};

        int[] val = {60, 40, 100, 120};

        int capacity = 50;

  

        double maxValue = getMaxValue(wt, val, capacity);

        System.out.println("Maximum value we can obtain = "

                            maxValue);

  

    }

  

    // функция для получения максимального значения

    private static double getMaxValue(int[] wt,

                        int[] val, int capacity)

    {

        ItemValue[] iVal = new ItemValue[wt.length];

  

        for(int i = 0; i < wt.length; i++)

        {

            iVal[i] = new ItemValue(wt[i], val[i], i);

        }

  

        // сортировка элементов по значению;

        Arrays.sort(iVal, new Comparator<ItemValue>() 

        {

            @Override

            public int compare(ItemValue o1, ItemValue o2) 

            {

                return o2.cost.compareTo(o1.cost) ;

            }

        });

  

  

        double totalValue = 0d;

  

        for(ItemValue i: iVal)

        {

  

            int curWt = (int) i.wt;

            int curVal = (int) i.val;

  

            if (capacity - curWt >= 0)

            {

                // этот вес можно выбрать, пока

                capacity = capacity-curWt;

                totalValue += curVal;

  

            }

            else

            {

                // элемент нельзя выбрать целиком

                double fraction = ((double)capacity/(double)curWt);

                totalValue += (curVal*fraction);

                capacity = (int)(capacity - (curWt*fraction));

                break;

            }

  

  

        }

  

        return totalValue;

    }

  

    // класс значения элемента

    static class ItemValue 

    {

        Double cost;

        double wt, val, ind;

          

        // функция значения элемента

        public ItemValue(int wt, int val, int ind)

        {

            this.wt = wt;

            this.val = val;

            this.ind = ind;

            cost = new Double(val/wt );

        }

    }

}

python3

# Python3 программа для решения дробных
# Рюкзак Проблема

class ItemValue:

      

    "" "Значение элемента DataClass" ""

    def __init__(self, wt, val, ind):

        self.wt = wt

        self.val = val

        self.ind = ind

        self.cost = val // wt

  

    def __lt__(self, other):

        return self.cost < other.cost

  
# Жадный подход

class FractionalKnapSack:

      

    "" "Сложность времени O (n log n)" ""

    @staticmethod

    def getMaxValue(wt, val, capacity):

          

        "" "функция для получения максимального значения" ""

        iVal = []

        for i in range(len(wt)):

            iVal.append(ItemValue(wt[i], val[i], i))

  

        # сортировка предметов по значению

        iVal.sort(reverse = True)

  

        totalValue = 0

        for i in iVal:

            curWt = int(i.wt)

            curVal = int(i.val)

            if capacity - curWt >= 0:

                capacity -= curWt

                totalValue += curVal

            else:

                fraction = capacity / curWt

                totalValue += curVal * fraction

                capacity = int(capacity - (curWt * fraction))

                break

        return totalValue

  
Код водителя

if __name__ == "__main__":

    wt = [10, 40, 20, 30]

    val = [60, 40, 100, 120]

    capacity = 50

  

    maxValue = FractionalKnapSack.getMaxValue(wt, val, capacity)

    print("Maximum value in Knapsack =", maxValue)

  
# Этот код предоставлен vibhu4agarwal


Выход :

Maximum value in Knapsack = 240

Поскольку основным этапом является сортировка, вся проблема может быть решена только за O (n log n).
Эта статья предоставлена Уткаршем Триведи.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Дробный рюкзак

0.00 (0%) 0 votes