Shortest/Cheapest Path? How to use dynamic programming here?

Question

I have a problem regarding dynamic programming. This is a shortest path problem. The premise is I need to help a "friend" write a program for the cheapest tiling he can use to build a path to his shed. The variables D (distance to the shed), can be 1 <= D < 5000, there can be N number of TYPES of tiles so that 1 <= N <= 5000, also for each "N" tile, there can be a length, L so that 1 <= L <=5000, and a cost, C so that 1 <= C <= 100. (The user of this program will follow the constraints listed above). I know this is a shortest path problem but I cannot figure out how to start the graph. I was thinking of making a 2d array with distance and types of tiles but thought against that. I'm pasting my code below, it works for test cases for error checking but other than that it does not. If someone could provide me with a hint as to what I am doing wrong or a hint as to how to start the graph, or just tell me that I am way off the mark, that would be great. I am refraining from using recursion because I want this program to run efficiently, that is why I want to use dynamic programming.

#include <iostream>
#include <utility>
#include <cstdlib>
#include <cstring>
#include <limits.h>
#include <cstdio>


using namespace std;

int cheapestTiling(int dist, int numtiles, int A[], int B[]){

    //distance to the shed
    int shedDistance = dist;
    //number of types of tiles used
    int numberTiles = numtiles;

    //make new arrays for the costs and lengths of each tiles
    int LengthTile[numberTiles];
    int PriceTile[numberTiles];
    int costPerSize[numberTiles];

    //min length, min price
    int minlength = 0;
    int minprice = 0;

    while (shedDistance != 0){

        for (int i = 0; i < nAumberTiles; i++){
            LengthTile[i] = A[i];
            PriceTile[i] = B[i];
            costPerSize[i] = (A[i]/B[i])

            while((LengthTile[i] > LengthTile[i+1])
            {
                if(shedDistance > lengthTile[i])
                {
                //here i'm trying to find the longer tile and use those first
                //I havent started worrying about the cost yet and am just focusing
                //on the length/distance aspect
                int tempTile = lengthTile[i];
                shedDistance = shedDistance - tempTile;
                }
               // else if((shedDistance < lengthTile[i]) && (lengthTile[i+1] < shedDistance))
            }

        }
        minlength = LengthTile[0];
 minprice = PriceTile[0];

        for(int i = 1; i < numberTiles; i++)
        {
            if(LengthTile[i] < minlength)
            {
                minlength = LengthTile[i];
            }
            if(PriceTile[i] < minprice)
            {
                minprice = PriceTile[i];
            }
        }

      //error check for shed distance = 1
      if (shedDistance == 1)
      {
          shedDistance = shedDistance - minlength;
          return minprice;
      }
      //error check for shed distance < 0
      else if (shedDistance < 0)
      {
     return 0;
      }

    }



}

int main (){


//distance to shed
int distance = 0;
//number of types of tiles used
int num = 0;
//the return of the total cost, the answer
int totalCost = 0;


//get distance to shed
 cin >> distance;
//get number of types of tiles
 cin >> num;

 //cost of each tile used
 int TileLength[num];
 int TilePrice[num];


for (int i = 0; i < num; i++)
{
    cin >> TileLength[i];
    cin >> TilePrice[i];
}

totalCost = cheapestTiling(distance, numTiles, TileLength, TilePrice);
cout << totalCost << endl;


}

Answer 1

This to me doesn't sound like a shortest path problem. It's more like a knapsack problem because I am assuming that you are trying to minimize the price while still reaching your goal distance.

en.wikipedia.org/wiki/Knapsack_problem

Hope I helped.