交叉相乘写性价比比较器

👁️ 2 人浏览 💬 0 人评论 ❤️ 添加收藏

补全 denser：每单位重量价值高的排前面，用交叉相乘比较，不要用除法。三件物品按 (5,20)(6,30)(5,20) 的顺序给出，补全后输出 0-1 背包贪心（容量 10）的总价值。

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

提交你的答案

请登录后提交答案。

去登录

← 用 lambda 写区间调度两个关键字的比较器 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

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

struct Item {
    int w, v;
};

bool denser(const Item& a, const Item& b) {
    // TODO: a.v / a.w > b.v / b.w 改写成交叉相乘，返回 a 是否该排在前
    (void)a; (void)b;
    return false;
}

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({{5, 20}, {6, 30}, {5, 20}}, 10) << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

🔒 登录并作答后可看讨论