写 0-1 背包的贪心

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

补全 knap_greedy：按每斤价值从高到低排（用 denser），装得下就整件拿走。输出总价值。

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

提交你的答案

请登录后提交答案。

去登录

← 能切开就不一样了写 0-1 背包的动态规划 →

更多题目

代码编辑器

语言： 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) {
    int v = 0;
    // TODO: 用 stable_sort 和 denser 排好，逐件判断装不装得下
    (void)items; (void)cap;
    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) << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

🔒 登录并作答后可看讨论