一个解法三个问题

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

数组 {10, 20, 15, 5}（总和 50）。三个看起来不一样的问题：能不能平分、能不能分成相差 10 的两堆、有没有子集和正好是 7。三个都归约到同一个 subset_sum。输出如 能/能/不能。

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

提交你的答案

请登录后提交答案。

去登录

← 归约做成了没有设计加证明该包含什么 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

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

#include <numeric>

bool subset_sum(const vector<int>& arr, int target) {   // 老朋友：能不能挑出子集，和正好是 target
    if (target < 0) return false;
    vector<bool> reach(target + 1, false);
    reach[0] = true;
    for (int x : arr) {
        for (int r = target; r >= x; r--) {
            if (reach[r - x]) reach[r] = true;
        }
    }
    return reach[target];
}

const vector<int> NO = {17, 24, 15, 13, 23};
const vector<int> YES = {10, 20, 15, 5};
const vector<int> ODD = {17, 24, 15, 13, 23, 3};

const vector<int> A4 = {10, 20, 15, 5};
const int S = 50;

bool can_split(const vector<int>& arr) { return S % 2 == 0 && subset_sum(arr, S / 2); }

bool can_diff(const vector<int>& arr, int d) {
    // TODO: 多的那一堆的和是 (S + d) / 2，除不尽就一定不行；否则交给 subset_sum
    (void)arr; (void)d;
    return false;
}

bool has_sum(const vector<int>& arr, int k) {
    // TODO: 有没有一个子集的和正好是 k——原样交给 subset_sum
    (void)arr; (void)k;
    return false;
}

int main() {
    cout << (can_split(A4) ? "能" : "不能") << "/" << (can_diff(A4, 10) ? "能" : "不能") << "/"
         << (has_sum(A4, 7) ? "能" : "不能") << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

一个解法三个问题

更多题目

全部评论