交付贪心解加正确性依据

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

这是这条路线的最终作品。前面写过的函数都已给好，只差区间调度和背包 DP 两处。一次验完五条：六场会按结束早 4 场、按开始早 1 场；25/10/5/1 找 63 贪心 6 枚且和最优一致；4/3/1 找 6 贪心 3 枚、最优 2 枚；四个任务穷举最小值和排好序的值相等；背包 0-1 贪心 30、0-1 最优 40、可切开 46。五条全过输出 验收通过，否则输出 验收失败。

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

提交你的答案

请登录后提交答案。

去登录

← 第四步背包三连对拍到底在验证什么 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

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

int greedy(const vector<int>& cs, int t) {
    // 面值已按从大到小给好：每次拿不超过剩下金额的最大面值
    int n = 0;
    for (int c : cs) {
        while (t >= c) {
            t -= c;
            n++;
        }
    }
    return n;
}

int best(const vector<int>& cs, int t) {
    // dp[a] = 凑够 a 最少要几枚
    const int INF = 1000000000;
    vector<int> dp(t + 1, INF);
    dp[0] = 0;
    for (int a = 1; a <= t; a++) {
        for (int c : cs) {
            if (c <= a && dp[a - c] + 1 < dp[a]) dp[a] = dp[a - c] + 1;
        }
    }
    return dp[t];
}

struct Seg {
    int s, e;
};

template <class Cmp>
int sched(vector<Seg> iv, Cmp cmp) {
    // TODO: 按 cmp 排好，从头挑，不重叠就要
    (void)iv; (void)cmp;
    return 0;
}

int wait_total(const vector<int>& order) {
    // 按给定顺序做任务：把每个任务的完成时刻加起来
    int t = 0;
    int s = 0;
    for (int x : order) {
        t += x;
        s += t;
    }
    return s;
}

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);
    // TODO: 每件物品一遍，容量倒着更新
    (void)items;
    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() {
    vector<bool> ok;
    ok.push_back(sched({{1, 4}, {2, 3}, {3, 5}, {0, 7}, {5, 6}, {6, 8}}, [](const Seg& a, const Seg& b) { return a.e < b.e; }) == 4 && sched({{1, 4}, {2, 3}, {3, 5}, {0, 7}, {5, 6}, {6, 8}}, [](const Seg& a, const Seg& b) { return a.s < b.s; }) == 1);
    ok.push_back(greedy({25, 10, 5, 1}, 63) == 6 && best({25, 10, 5, 1}, 63) == 6);
    ok.push_back(greedy({4, 3, 1}, 6) == 3 && best({4, 3, 1}, 6) == 2);
    vector<int> p = {1, 2, 3, 4};
    int m = 1000000000;
    do {
        m = min(m, wait_total(p));
    } while (next_permutation(p.begin(), p.end()));
    ok.push_back(m == wait_total({1, 2, 3, 4}));
    ok.push_back(knap_greedy({{6, 30}, {5, 20}, {5, 20}}, 10) == 30 && knap_dp({{6, 30}, {5, 20}, {5, 20}}, 10) == 40 && knap_frac({{6, 30}, {5, 20}, {5, 20}}, 10) == 46);
    bool all = true;
    for (bool b : ok) all = all && b;
    cout << (all ? "验收通过" : "验收失败") << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

交付贪心解加正确性依据

更多题目

全部评论