fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <functional>
  5. #include <climits>
  6. using namespace std;
  7.  
  8. const int MAX = 5;
  9. const int COMBINATION_SIZE = 5;
  10.  
  11. struct Supply {
  12.     int value;
  13.     int row;
  14.     int col;
  15. };
  16.  
  17. int resupply(int shortfall, int supply[MAX][MAX]) {
  18.     vector<Supply> supplies;
  19.  
  20.     // Chuyển ma trận thành vector các ô tiếp tế
  21.     for (int i = 0; i < MAX; ++i) {
  22.         for (int j = 0; j < MAX; ++j) {
  23.             supplies.push_back({supply[i][j], i, j});
  24.         }
  25.     }
  26.  
  27.     // Sắp xếp vector theo giá trị tiếp tế tăng dần
  28.     sort(supplies.begin(), supplies.end(), [](const Supply &a, const Supply &b) {
  29.         return a.value < b.value;
  30.     });
  31.  
  32.     int min_total = INT_MAX;
  33.     vector<int> result_indices;
  34.  
  35.     // Sử dụng hồi quy để tìm tất cả các tổ hợp hợp lệ và chọn tổ hợp có tổng giá trị nhỏ nhất
  36.     function<void(int, int, int, vector<int>&)> find_combinations = [&](int start, int k, int sum, vector<int>& indices) {
  37.         if (k == 0) {
  38.             if (sum >= shortfall && sum < min_total) {
  39.                 min_total = sum;
  40.                 result_indices = indices;
  41.             }
  42.             return;
  43.         }
  44.  
  45.         for (int i = start; i <= supplies.size() - k; ++i) {
  46.             indices.push_back(i);
  47.             find_combinations(i + 1, k - 1, sum + supplies[i].value, indices);
  48.             indices.pop_back();
  49.         }
  50.     };
  51.  
  52.     vector<int> indices;
  53.     find_combinations(0, COMBINATION_SIZE, 0, indices);
  54.  
  55.     // Trả về tổng giá trị của 5 ô được chọn
  56.     return min_total;
  57. }
  58.  
  59. int main() {
  60.     int shortfall = 1050;
  61.     int supply[MAX][MAX] = {
  62.         {150, 200, 180, 90, 110},
  63.         {70, 80, 120, 140, 160},
  64.         {220, 240, 200, 190, 130},
  65.         {100, 110, 300, 280, 320},
  66.         {170, 210, 260, 230, 290}
  67.     };
  68.  
  69.     int result = resupply(shortfall, supply);
  70.     cout << "Tổng tiếp tế của 5 ô được chọn: " << result << endl;
  71.  
  72.     return 0;
  73. }
  74.  
Success #stdin #stdout 0.01s 5256KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Tổng tiếp tế của 5 ô được chọn: 1050
https://ideone.com/QppRI7
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!