三个数摆在一起看

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

同一批物品、同一个容量，一次输出三个数：0-1 贪心 / 0-1 最优 / 可切开的贪心。

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

提交你的答案

请登录后提交答案。

去登录

← 写可以切开的背包交换论证在证明什么（C++） →

更多题目

代码编辑器

语言： 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) {
    // 每单位重量的价值更高的排前面；交叉相乘，避开小数
    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() {
    // TODO: 三个函数各跑一遍（物品 {{6, 30}, {5, 20}, {5, 20}}、容量 10），用 / 拼起来输出
}

本次输入：

输出：

👩‍🏫

💬 题目评论

🔒 登录并作答后可看讨论