最短/最短経路ですか？ここで動的プログラミングを使用するには？

Question

私は動的プログラミングに関する問題があります。これは最短経路問題です。私は、 "友人"が彼の倉庫への道を築くために使うことができる最も安いタイル張りのプログラムを書くのを助ける必要があることを前提にしています。変数D（杼口までの距離）は、1 < = D < 5000とすることができ、1つの「N」タイルごとに1 < = N < = 5000となるようにN個のタイルタイプが存在することができる。長さLは、1 < = L < = 5000、コストはCとなるように1 < = C < = 100となります（このプログラムのユーザーは上記の制約に従います）。私はこれが最短経路問題であることを知っていますが、私はグラフをどのように開始するのか分かりません。私は距離とタイルの種類を持つ2次元配列を作ることを考えていましたが、それに対して考えました。私は以下のコードを貼り付けていますが、エラーチェックのためのテストケースでは動作しますが、それ以外のケースでは動作しません。誰かが、私が間違ってやっていることや、グラフを始める方法のヒントを私に知らせることができた場合、あるいは私がマークから離れていることを教えてください。このプログラムを効率的に実行したいので、再帰を使用しないことを控えています。そのため、動的プログラミングを使いたいのです。

#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

希望私が助けました。