최단 경로/최저 경로? 여기서 동적 프로그래밍을 사용 하시겠습니까?

Question

동적 프로그래밍 관련 문제가 있습니다. 이것은 최단 경로 문제입니다. 전제는 "친구"가 자신의 창고로가는 길을 만드는 데 사용할 수있는 가장 저렴한 타일링 프로그램을 작성하는 데 도움이 필요합니다. 변수 D (창고까지의 거리)는 1 < = D < 5000이 될 수 있으며, N 개의 타일 유형이있어 1 < = N < = 5000이 될 수 있으며 각 "N"타일에도 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

희망 나는 도왔다.