En Kısa/En Ucuz Yol? Dinamik programlama nasıl kullanılır?

Question

Dinamik programlama ile ilgili bir sorunum var. Bu en kısa yol problemidir. Önceleri, bir "arkadaş" ın, kulübesine bir yol inşa etmek için kullanabileceği en ucuz döşeme için bir program yazmasına yardım etmem gerekiyor. Değişkenler D (çukura olan mesafe), 1 < = D < 5000 olabilir, her bir "N" kiremit için de 1 < = N < = 5000 olacak şekilde ÇİN TİPİ sayısı N olabilir. 1 < = L < = 5000 ve bu nedenle, 1 < = C < = 100 (bu programın kullanıcısı yukarıda listelenen kısıtlamaları izleyecektir). Bunun en kısa yol problemi olduğunu biliyorum ancak grafiğin nasıl başlatılacağını anlayamıyorum. Uzaklık ve çini türleriyle 2 boyutlu bir dizi yapmayı düşünüyordum ama buna karşı düşündüm. Aşağıda kodumu yapıştırıyorum, hata denetimi için test durumları için çalışır, ancak bunun dışında çalışır. Birisi bana yanlış yaptığım ya da grafiğin nasıl başlatılacağına dair bir ipucu verebilirse ya da sadece bana işaretin dışında olduğumu söylerse, bu harika olur. Yinelemeyi kullanmaktan vazgeçiyorum çünkü bu programın verimli çalışmasını istiyorum, bu yüzden dinamik programlama kullanmak istiyorum.

#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

Bu bana en kısa yol sorunu gibi gelmiyor. Daha çok bir sırt çantası problemi gibi çünkü fiyatınızı en aza indirmeye çalışırken hedef mesafenize ulaşmaya çalışıyorsunuz.

en.wikipedia.org/wiki/Knapsack_problem

Umut ben yardımcı oldu.