Kürzester/Günstigster Weg? Wie benutzt man dynamische Programmierung hier?

Question

Ich habe ein Problem in Bezug auf dynamische Programmierung. Dies ist ein Problem mit dem kürzesten Pfad. Die Voraussetzung ist, dass ich einem "Freund" helfen muss, ein Programm für die billigsten Fliesen zu schreiben, die er benutzen kann, um einen Weg zu seinem Schuppen zu bauen. Die Variablen D (Abstand zum Schuppen), kann sein 1 < = D < 5000, es kann N Anzahl von TYPEN von Kacheln sein, so dass 1 < = N < = 5000, auch für jede "N" Kachel kann es a Länge, L so, dass 1 < = L < = 5000, und eine Kosten, C, so dass 1 < = C < = 100. (Der Benutzer dieses Programms wird die oben aufgeführten Einschränkungen beachten). Ich weiß, dass dies ein Problem mit dem kürzesten Pfad ist, aber ich kann nicht herausfinden, wie ich den Graphen starten soll. Ich dachte daran, ein 2D-Array mit Abstand und Arten von Fliesen zu machen, dachte aber dagegen. Ich schreibe meinen Code unten, es funktioniert für Testfälle zur Fehlerprüfung, aber ansonsten nicht. Wenn mir jemand einen Hinweis geben könnte, was ich falsch mache, oder einen Hinweis, wie ich den Graphen starten soll, oder mir einfach sagen soll, dass ich weit davon entfernt bin, wäre das großartig. Ich verzichte auf Rekursion, weil ich möchte, dass dieses Programm effizient läuft, deshalb möchte ich dynamische Programmierung verwenden.

#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

Das klingt für mich nicht wie ein kürzester Weg Problem. Es ist eher ein Rucksackproblem, weil ich annehme, dass Sie versuchen, den Preis zu minimieren, während Sie immer noch Ihre Zieldistanz erreichen.

en.wikipedia.org/wiki/Knapsack_problem

Hoffnung half ich.