paiza Aランク相当 「お菓子の詰め合わせ」

問題文

解法

動的計画法

ぱっと見で思いつくのはこれですかね
制約は小さいので余裕で間に合う。計算量O(N ^ 2 * X)かな？

dp.cpp

#include <bits/stdc++.h>
using namespace std;



int main() {
    int N, X;
    cin >> N >> X;
    
    vector<vector<bool>>dp(X + 1, vector<bool>(N + 1));
    dp[0][0] = true;
    
    for(int i = 0; i < N; i++){
        vector<vector<bool>>ndp(X + 1, vector<bool>(N + 1));
        int x;
        cin >> x;
        for(int j = 0; j < X + 1; j++){
            for(int k = 0; k < N + 1; k++){
                if(dp[j][k]){
                    ndp[j][k] = true;
                    if(j + x < X + 1 and k + 1 < N + 1) ndp[j + x][k + 1] = true;
                }
            }
        }
        swap(dp, ndp);
    }

    for(int i = N; i >= 0; i--){
        for(int j = X; j > 0; j--){
            if(dp[j][i]){
                cout << X - j << endl;
                return 0;
            }
        }
    }
}

深さ優先探索

N=20なので買うか買わないかで愚直に探索して間に合う。計算量は2^20
めんどいのでグローバルに変数書いた事については勘弁してください。

dfs.cppp

#include <bits/stdc++.h>
using namespace std;

int N, X;
vector<int>x;

void dfs(int i, int sum, int type, vector<vector<bool>> &flag){

    if(i == N){
        if(type == 0) return;
        if(sum > X)return;
        flag[sum][type] = true;
        return;
    }

    dfs(i + 1, sum + x[i], type + 1, flag);
    dfs(i + 1, sum, type, flag);

    return;
}


int main() {
    cin >> N >> X;
    
    x.resize(N);
    for(int i = 0; i < N; i++) cin >> x[i];
    
    vector<vector<bool>>flag(X + 1, vector<bool>(N + 1));
    dfs(0, 0, 0, flag);

    for(int i = N; i >= 0; i--){
        for(int j = X; j > 0; j--){
            if(flag[j][i]){
                cout << X - j << endl;
                return 0;
            }
        }
    }
}

半分全列挙

こんな事をやる必要ない問題ですが、最近書いてなかったので練習で書きました。
無駄にややこしいためコードが汚いのは勘弁してください。
深さ優先だと間に合わないN=40あたりでも間に合います。（問題の制約はN=20だけど)

split.cpp

#include <bits/stdc++.h>
using namespace std;



int main() {
    int N, X;
    cin >> N >> X;
    
    vector<int>x(N);
    for(int i = 0; i < N; i++) cin >> x[i];

    int hn = N / 2;
    vector<vector<int>>x0(N + 1);
    
    for(int bit = 0; bit < (1 << hn); bit++){
            int tmp = 0;
            int cnt = 0;
            for(int i = 0; i < hn; i++){
                if(bit >> i & 1) tmp += x[i], cnt++;
            }
            x0[cnt].push_back(tmp);
    }

    

    for(int i = 0; i < N + 1; i++) sort(x0[i].begin(), x0[i].end());

    pair<int,int>ans = pair<int, int>(0, 0);
    for(int bit = 0; bit < (1 << (N - hn)); bit++){
        int tmp = 0;
        int cnt = 0;
        for(int i = 0; i < (N - hn); i++){
            if(bit >> i & 1) tmp += x[hn + i], cnt++;
        }
        int d = min(hn, N - cnt);
        for(int i = d; i >= 0; i--){
            if(i == 0 and tmp == 0) break;
            if(ans.second > i + cnt) break;
            auto iter = upper_bound(x0[i].begin(), x0[i].end(), X - tmp);
            if(iter == x0[i].begin()) continue;
            if(ans.second == i + cnt and ans.first < tmp + *prev(iter)){
                ans = pair<int, int>(tmp + *prev(iter), i + cnt);
                break;
            }else if(ans.second < i + cnt){
                ans = pair<int, int>(tmp + *prev(iter), i + cnt);
                break;
            }
        }
    }

    cout << X - ans.first << endl;
}