fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. using namespace std;
  5.  
  6. const int INF = 1e9;
  7.  
  8. int main() {
  9.     cout << "=============================================\n";
  10.     cout << " OPTIMASI PENGIRIMAN PAKET DRONE (DP)\n";
  11.     cout << "=============================================\n\n";
  12.  
  13.  
  14.     // INPUT DATA
  15.  
  16.     vector<int> jarak = {2, 3, 3, 4, 5, 6}; 
  17.     int K = 7;                             
  18.     int N = jarak.size();
  19.  
  20.     cout << "Jumlah pelanggan: " << N << endl;
  21.     cout << "Kapasitas baterai drone: " << K << endl;
  22.     cout << "Jarak pelanggan: ";
  23.     for(int d : jarak) cout << d << " ";
  24.     cout << "\n\n";
  25.  
  26.  
  27.     // PRECOMPUTE SUBSET VALID
  28.  
  29.     int TOTAL = 1 << N;
  30.     vector<int> subsetValid; 
  31.     vector<int> subsetJarak(TOTAL, 0);
  32.  
  33.     for(int mask = 1; mask < TOTAL; mask++) {
  34.         int sum = 0;
  35.         for(int i = 0; i < N; i++) {
  36.             if(mask & (1 << i)) {
  37.                 sum += jarak[i];
  38.             }
  39.         }
  40.         subsetJarak[mask] = sum;
  41.         if(sum <= K) {
  42.             subsetValid.push_back(mask);
  43.         }
  44.     }
  45.  
  46.  
  47.     // DP BITMASK
  48.  
  49.     vector<int> dp(TOTAL, INF);
  50.     vector<int> prevMask(TOTAL, -1);
  51.     vector<int> paketDipilih(TOTAL, -1);
  52.  
  53.     dp[0] = 0;
  54.  
  55.     for(int mask = 0; mask < TOTAL; mask++) {
  56.         if(dp[mask] == INF) continue;
  57.  
  58.         for(int sMask : subsetValid) {
  59.             int newMask = mask | sMask;
  60.             if(dp[newMask] > dp[mask] + 1) {
  61.                 dp[newMask] = dp[mask] + 1;
  62.                 prevMask[newMask] = mask;
  63.                 paketDipilih[newMask] = sMask;
  64.             }
  65.         }
  66.     }
  67.  
  68.     int finalMask = TOTAL - 1;
  69.  
  70.  
  71.     //HASIL
  72.  
  73.     cout << "Jumlah perjalanan minimal = " << dp[finalMask] << "\n\n";
  74.  
  75.     cout << "Rincian Pengiriman:\n";
  76.     cout << "-------------------\n";
  77.  
  78.     vector<int> urutan;
  79.     int mask = finalMask;
  80.  
  81.     while(mask != 0) {
  82.         urutan.push_back(paketDipilih[mask]);
  83.         mask = prevMask[mask];
  84.     }
  85.  
  86.     int trip = 1;
  87.     for(int i = urutan.size()-1; i >= 0; i--) {
  88.         int sMask = urutan[i];
  89.         cout << "Perjalanan " << trip++ << " : ";
  90.         int totalJ = 0;
  91.  
  92.         for(int j = 0; j < N; j++) {
  93.             if(sMask & (1 << j)) {
  94.                 cout << "Pelanggan-" << (j+1) << "(jarak " << jarak[j] << ") ";
  95.                 totalJ += jarak[j];
  96.             }
  97.         }
  98.         cout << " -> Total jarak: " << totalJ << endl;
  99.     }
  100.  
  101.     cout << "\nSemua paket berhasil dikirim!\n";
  102.     cout << "=============================================\n";
  103.  
  104.     return 0;
  105. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
=============================================
 OPTIMASI PENGIRIMAN PAKET DRONE (DP)
=============================================

Jumlah pelanggan: 6
Kapasitas baterai drone: 7
Jarak pelanggan: 2 3 3 4 5 6 

Jumlah perjalanan minimal = 4

Rincian Pengiriman:
-------------------
Perjalanan 1 : Pelanggan-2(jarak 3)  -> Total jarak: 3
Perjalanan 2 : Pelanggan-3(jarak 3) Pelanggan-4(jarak 4)  -> Total jarak: 7
Perjalanan 3 : Pelanggan-1(jarak 2) Pelanggan-5(jarak 5)  -> Total jarak: 7
Perjalanan 4 : Pelanggan-6(jarak 6)  -> Total jarak: 6

Semua paket berhasil dikirim!
=============================================
https://ideone.com/1It264
language:
C++14 (clang 8.0)
created:
9 hours 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!