結果
問題 | No.2869 yuusaan's Knapsacks |
ユーザー |
|
提出日時 | 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 |
ソースコード
#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; }