fork download
copy 
  1. //
  2. //  main.cpp
  3. //  Modified Knapsack
  4. //
  5. //  Created by Himanshu on 29/10/18.
  6. //  Copyright © 2018 Himanshu. All rights reserved.
  7. //
  8.  
  9. #include <iostream>
  10. #include <vector>
  11. using namespace std;
  12.  
  13. int solve(vector<int> a, int K) {
  14.     int n = (int)a.size(), totalDistance = 0;
  15.     int dp[n+1][K+1], caveTaken[n+1][K+1];
  16.     for (int i = 0; i <= n; i++) {
  17.         for (int j = 0; j <= K; j++) {
  18.             dp[i][j] = 0;
  19.             caveTaken[i][j] = -1;
  20.         }
  21.     }
  22.  
  23.     for (int i = 0; i < n; i++) {
  24.         totalDistance = totalDistance + a[i];
  25.     }
  26.  
  27.     for (int i = 0; i <= n; i++) {
  28.         for (int j = 0; j <= K; j++) {
  29.             if (i == 0 || j == 0) {
  30.                 dp[i][j] = 0;
  31.             } else {
  32.                 dp[i][j] = dp[i-1][j];
  33.                 // If optimal solution include current cave
  34.                 if (dp[i-1][j] < (a[i-1] + dp[i-1][j-1])) {
  35.                     // If current optimal solution
  36.                     // include previous cave
  37.                     if (caveTaken[i-1][j-1] != -1) {
  38.                         if (i > 1) {
  39.                             dp[i][j] = max(dp[i-1][j], a[i-1] + dp[i-2][j-1]);
  40.                             if (dp[i][j] != dp[i-1][j]) {
  41.                                 caveTaken[i][j] = i-1;
  42.                             }
  43.                         }
  44.                     } // If current optimal solution doesn't include
  45.                       // previous cave
  46.                     else {
  47.                         dp[i][j] = a[i-1] + dp[i-1][j-1];
  48.                         caveTaken[i][j] = i-1;
  49.                     }
  50.                 }
  51.             }
  52.         }
  53.     }
  54.  
  55.     return (totalDistance - dp[n][K]);
  56. }
  57.  
  58. int main(int argc, const char * argv[]) {
  59.     vector<int> a = {10, 12, 11, 18};
  60.     int K = 2;
  61.     cout<<"Minimum distance to travel: "<<solve(a, K)<<endl;
  62.     return 0;
  63. }
  64.  
Success #stdin #stdout 0.01s 5624KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Minimum distance to travel: 21
https://ideone.com/QfB0Yr
language:
C++ 4.3.2 (gcc-4.3.2)
created:
3 years ago
visibility:
secret

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!