結果

問題 No.2869 yuusaan's Knapsacks
コンテスト
ユーザー yuusaan
提出日時 2024-07-18 12:31:45
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,759 bytes
コンパイル時間 1,165 ms
コンパイル使用メモリ 102,360 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-08-04 18:03:24
合計ジャッジ時間 3,709 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
other AC * 16 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

struct Item {
    int value;
    int weight;
};

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> e(N);
    for (int i = 0; i < N; ++i) {
        cin >> e[i];
    }

    vector<Item> items(M);
    for (int i = 0; i < M; ++i) {
        cin >> items[i].value >> items[i].weight;
    }

    int max_combinations = 1 << M; // 2^M combinations
    vector<int> dp(max_combinations, -1);
    vector<int> combination(max_combinations, 0);
    dp[0] = 0;

    for (int mask = 0; mask < max_combinations; ++mask) {
        if (dp[mask] == -1) continue;
        for (int i = 0; i < M; ++i) {
            if (!(mask & (1 << i))) { // if i-th item is not in the current combination
                int new_mask = mask | (1 << i);
                int new_value = dp[mask] + items[i].value;
                if (new_value > dp[new_mask]) {
                    dp[new_mask] = new_value;
                    combination[new_mask] = i;
                }
            }
        }
    }

    int max_value = 0;
    int best_combination = 0;
    for (int mask = 0; mask < max_combinations; ++mask) {
        if (dp[mask] > max_value) {
            bool valid = true;
            vector<int> total_weight(N, 0);
            for (int i = 0; i < M; ++i) {
                if (mask & (1 << i)) {
                    int selected_bag = 0;
                    for (int j = 0; j < N; ++j) {
                        if (total_weight[j] + items[i].weight <= e[j]) {
                            total_weight[j] += items[i].weight;
                            break;
                        }
                        selected_bag++;
                    }
                    if (selected_bag == N) {
                        valid = false;
                        break;
                    }
                }
            }
            if (valid) {
                max_value = dp[mask];
                best_combination = mask;
            }
        }
    }

    cout << max_value << endl;
    vector<vector<int>> bag_items(N);
    for (int i = 0; i < M; ++i) {
        if (best_combination & (1 << i)) {
            for (int j = 0; j < N; ++j) {
                int total_weight = 0;
                for (auto &item : bag_items[j]) {
                    total_weight += items[item].weight;
                }
                if (total_weight + items[i].weight <= e[j]) {
                    bag_items[j].push_back(i);
                    break;
                }
            }
        }
    }

    for (int i = 0; i < N; ++i) {
        cout << bag_items[i].size();
        for (auto &item : bag_items[i]) {
            cout << " " << item + 1;
        }
        cout << endl;
    }

    return 0;
}
0