Условие задачи

Есть рюкзак, вместимость которого $W$ грамм ($W$ - целое число) и $K$ предметов весом $wi$ грамм и стоимостью $ci$ за грамм. Можно брать от любого предмета целое количество грамм. Необходимо набрать рюкзак максимальной стоимости.

---

Решение

Найдём для каждого предмета отношение $ci / wi$. Отсортируем все предметы по этому отношению​​ и будем брать их жадно в таком порядке. Если последний предмет не влезает полностью, тогда от него будем брать только часть.

---

Сложность

Сложность алгоритма - $О(K) + K*log_2 K$.

---

Псевдокод

Функция_вычисления(вместимость, количество, цена, вес)
    предметы <- пустой список
    
    для i в диапазоне количество
        в предметы добавить пару из цены и веса
    
    сортировать предметы по соотношению цена/вес

    ответ <- 0
    
    для i в диапазоне количество
        ответ <- цена предмета * минимум(вес предмета, вместимость)
        вместимость <- вместимость - минимум(вес предмета, вместимость)
        
    вернуть ответ

---

Реализация на Python

Аннотация:
backpack - функция для вычисления максимальной ценности предметов, которые можно поместить в рюкзак
W - общая вместимость рюкзака
K - количество предметов
c - список стоимостей предметов
w - список весов предметов
items - список кортежей, каждый из которых содержит стоимость и вес предмета
res - переменная для хранения общей ценности предметов в рюкзаке

def backpack(W, K, c, w):  
    items = list()  
    
    for i in range(K):  
        items.append((c[i], w[i]))  
  
    items = sorted(items, key=lambda x: x[0]/x[1], reverse=True)  
  
    res = 0  
    
    for i in range(K):  
        res += min(items[i][1], W) * items[i][0]  
        W -= min(items[i][1], W)  
        
    return res

---

Олимпиадная реализация на C++

Аннотация:
comp - функция для сравнения пар стоимости и веса, возвращающая `true`, если отношение стоимости к весу первой пары больше, чем у второй пары
p_w_1 - первая пара стоимости и веса
p_w_2 - вторая пара стоимости и веса
backpack - функция для вычисления максимальной ценности предметов, которые можно поместить в рюкзак
W - общая вместимость рюкзака
K - количество предметов
c - вектор стоимостей предметов
w - вектор весов предметов
items - вектор пар, каждая из которых содержит стоимость и вес предмета
res - переменная для хранения общей стоимости предметов в рюкзаке

typedef vector<int> vi;
typedef vector<pair<int, int>> vii;
typedef pair<double, double> dd;

bool comp(dd p_w_1, dd p_w_2) {
    return p_w_1.first / p_w_1.second >  p_w_2.first / p_w_2.second;
}

int backpack(int W, int K, vi c, vi w) {  
    vii items;
    
    for (int item = 0; item < K; ++item) 
        items.push_back(make_pair(c[item], w[item]));
    sort(items.begin(), items.end(), comp);
    
    int res = 0;
    
    for (int item = 0; item < K; ++item) {
        res += min(items[item].second, W) * items[item].first;
        W -= min(items[item].second, W);
    }
    
    return res;
}

---

Продуктовая реализация на C++

Аннотация:
compare - функция для сравнения пар стоимости и веса, возвращающая `true`, если отношение стоимости к весу первой пары больше, чем у второй пары
pair_1 - первая пара стоимости и веса
pair_2 - вторая пара стоимости и веса
backpack - функция для вычисления максимальной стоимости предметов, которые можно поместить в рюкзак
capacity - общая вместимость рюкзака
count_items - количество предметов
price_items - вектор стоимостей предметов
weight_items - вектор весов предметов
items - вектор пар, каждая из которых содержит стоимость и вес предмета
amount - переменная для хранения общей стоимости предметов в рюкзаке

bool compare(pair<double, double> pair_1, pair<double, double> pair_2) {
    return pair_1.first / pair_1.second >  pair_2.first / pair_2.second;
}

int backpack(int capacity, int count_items, 
             vector<int> price_items, vector<int> weight_items) {  
    vector<pair<int, int>> items;
    
    for (int item = 0; item < count_items; ++item) {
        items.push_back(make_pair(price_items[item], 
                                  weight_items[item]));
    }
    
    sort(items.begin(), items.end(), compare);
    
    int amount = 0;
    
    for (int item = 0; item < count_items; ++item) {
        int current_weight = min(items[item].second, capacity);
        amount += current_weight * items[item].first;
        capacity -= current_weight;
    }
    
    return amount;
}