写可以切开的背包

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

补全 knap_frac：同样按每斤价值排，装得下就整件拿，装不下就切一块把包填满（切下来的价值用 it.v * cap / it.w）。

（本题用 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) {
    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) {
    int v = 0;
    // TODO: 按 denser 排；装得下整件拿，装不下切一块填满就 break
    (void)items; (void)cap;
    return v;
}

int main() {
    cout << knap_frac({{6, 30}, {5, 20}, {5, 20}}, 10) << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

🔒 登录并作答后可看讨论