装不下的背包贪心和最优

背包能装 10，三件物品（重量, 价值）是 (6,30)(5,20)(5,20)，每件要么整件拿走要么不拿。

运行下面这段程序：

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct Item {
    int w, v;
};

bool denser(const Item& a, const Item& b) {
    // 每单位重量的价值更高的排前面；交叉相乘，避开小数
    return a.v * b.w > b.v * a.w;
}

int knap_greedy(vector<Item> items, int cap) {
    stable_sort(items.begin(), items.end(), denser);
    int v = 0;
    for (const Item& it : items) {
        if (it.w <= cap) {
            cap -= it.w;
            v += it.v;
        }
    }
    return v;
}

int knap_dp(const vector<Item>& items, int cap) {
    vector<int> dp(cap + 1, 0);
    for (const Item& it : items) {
        for (int c = cap; c >= it.w; c--) {
            if (dp[c - it.w] + it.v > dp[c]) dp[c] = dp[c - it.w] + it.v;
        }
    }
    return dp[cap];
}

int knap_frac(vector<Item> items, int cap) {
    stable_sort(items.begin(), items.end(), denser);
    int v = 0;
    for (const Item& it : items) {
        if (it.w <= cap) {
            cap -= it.w;
            v += it.v;
        } else {
            v += it.v * cap / it.w;
            cap = 0;
            break;
        }
    }
    return v;
}

int main() {
    cout << knap_greedy({{6, 30}, {5, 20}, {5, 20}}, 10) << "/" << knap_dp({{6, 30}, {5, 20}, {5, 20}}, 10) << endl;
}

（本题用 g++ -std=c++17 -O0 编译。）