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

我对动态编程有疑问。这是最短路径的问题。前提是我需要帮助一个“ friend ”编写一个程序，以便他可以使用最便宜的平铺方式建立自己的棚屋路径。变量D(到棚的距离)可以是1

#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;


}

最佳答案

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

en.wikipedia.org/wiki/Knapsack_problem

希望我能帮上忙。

关于c++ - 最短/最便宜的路径？在这里如何使用动态编程？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20080211/