Problem
Alansh has to travel through a road having hills of different heights. Also each hill has a cave to pass through it, to avoid travelling extra distance of a hill. Alansh wants to travel through this road by taking at most K caves, so that he has to travel minimum distance. However, if Alansh has taken cave i, he cannot take i+1 cave.
So, help Alansh to travel minimum distance using at most K number of caves. Also there’s no limit to distance travelled through caves and road. This distance is not counted.
Example 1:
Input:
a = {10, 12, 11, 18}
K = 2
Output: 21
Explanation:
Taking the cave through hills 12 and 18, gives the minimum distance to travel ie. 10+11 = 21
Optimal Substructure
An optimal solution to problem contain optimal solution to subproblems. To consider all caves, 2 cases for every cave arises:
- Cave is taken in optimal path
- Cave is not taken in optimal path
Approach
Now let’s modify the problem to this: Find the maximum distance travelled through the hills that could be avoided. Now this problem is same as Knapsack problem (or could also be solved by using a Greedy approach – selecting caves through tallest K hills).
However if the condition: if cave i is taken, he cannot take i+1 cave, hadn’t been there, this could have been solved by the above Greedy approach.
But to solve this problem with this additional constraint, we need to maintain an additional array val[n][K] to check if the previous cave was taken in this optimal solution of the subproblem.
After finding the maximum distance travelled through the hills that could be avoided, we could find our solution as:
Minimum distance travelled = total distance through all hills – maximum distance through hills
Code Implementation
//
// main.cpp
// Modified Knapsack
//
// Created by Himanshu on 29/10/18.
//
#include <iostream>
#include <vector>
using namespace std;
int solve(vector<int> a, int K) {
int n = (int)a.size(), totalDistance = 0;
int dp[n+1][K+1], caveTaken[n+1][K+1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= K; j++) {
dp[i][j] = 0;
caveTaken[i][j] = -1;
}
}
for (int i = 0; i < n; i++) {
totalDistance = totalDistance + a[i];
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= K; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
} else {
dp[i][j] = dp[i-1][j];
// If optimal solution include current cave
if (dp[i-1][j] < (a[i-1] + dp[i-1][j-1])) {
// If current optimal solution
// include previous cave
if (caveTaken[i-1][j-1] != -1) {
if (i > 1) {
dp[i][j] = max(dp[i-1][j], a[i-1] + dp[i-2][j-1]);
if (dp[i][j] != dp[i-1][j]) {
caveTaken[i][j] = i-1;
}
}
}
// If current optimal solution doesn't include
// previous cave
else {
dp[i][j] = a[i-1] + dp[i-1][j-1];
caveTaken[i][j] = i-1;
}
}
}
}
}
return (totalDistance - dp[n][K]);
}
int main() {
vector<int> a = {10, 12, 11, 18};
int K = 2;
cout<<"Minimum distance to travel: "<<solve(a, K)<<endl;
return 0;
}
Output
Minimum distance to travel: 21
Here’s a working example: Ideone