最短/最便宜的路径？如何在这里使用动态编程？

Question

我有关于动态编程的问题.这是一个最短的路径问题.前提是我需要帮助一个"朋友"为最便宜的平铺编写一个程序,他可以用它来建立一个通往他棚屋的路径.变量D(到棚屋的距离),可以是1 <= D <5000,可以有N个类型的瓦片,因此1 <= N <= 5000,对于每个"N"瓦片,可以有一个长度,L使得1 <= L <= 5000,并且成本,C使得1 <= C <= 100.(该程序的用户将遵循上面列出的约束).我知道这是一个最短的路径问题,但我无法弄清楚如何启动图表.我正在考虑制作一个带有距离和瓷砖类型的二维数组但是反过来考虑.我正在粘贴下面的代码,它适用于错误检查的测试用例,但不包括它.如果有人可以向我提供关于我做错了什么的暗示,或者提示如何启动图表,或者只是告诉我我的方法不合适,那就太棒了.我没有使用递归,因为我希望这个程序有效运行,这就是我想使用动态编程的原因.

#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

对我来说，这听起来不像是最短路径问题。这更像是一个背包问题，因为我假设您正在尝试最小化价格，同时仍达到目标距离。

en.wikipedia.org/wiki/Knapsack_problem

希望我有所帮助。