ronith
10/30/2018 - 3:28 AM

Doctor's Energy

Initially you have H amount of energy and D distance to travel. You may travel with any of the given 5 speeds. But you may only travel in units of 1 km. For each km distance traveled, you will spend corresponding amount of energy. e.g. the given speeds are: Cost of traveling 1 km: [4, 5, 2, 3, 6] Time taken to travel 1 km: [200, 210, 230, 235, 215] Find minimum time required to cover total D km with remaining H >= 0 1 <= H <= 4000 1 <= D <= 1000

Doctors Energy.cpp
content_copyfile_download
#include <iostream>
#include <string.h>
using namespace std;

int dp[4001][1001][5];

int func (int e, int d, int k, int cost[], int time[]) {
    if (e<0)
        return 100000;
    if (d==0)
        return 0;
    if (k<0)
        return 100000;
    if (dp[e][d][k]!= -1)
        dp[e][d][k];

    dp[e][d][k]= min(func(e,d,k-1, cost, time), time[k]+func(e-cost[k],d-1,k,cost, time));

    return dp[e][d][k];
}

int main() {
    int d=4, e=14;
    int cost[]= {4,5,2,3,6};
    int time[] = {200,210,230,235,215};

    memset(dp, -1, sizeof(dp));

    cout<< func(e,d,4,cost, time);

    cout<< "\n";
}