c++ - 最短/最便宜的路径？这里如何使用动态规划？

Question

我有一个关于动态规划的问题。这是一个最短路径问题。前提是我需要帮助一个“ friend ”写一个程序，用最便宜的瓷砖铺设一条通往他棚子的小路。变量 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

希望我有所帮助。