dynamic-programming
Rod snijden

De hengel snijden om de maximale winst te behalen

Gegeven een staaf met lengte n inches en een reeks lengte m van prijzen die prijzen bevat van alle stukken kleiner dan n. We moeten de maximaal haalbare waarde vinden door de stang in stukken te snijden en de stukken te verkopen. Als de lengte van de staaf bijvoorbeeld 8 is en de waarden van verschillende stukken als volgt worden gegeven, is de maximaal verkrijgbare waarde 22 .

       +---+---+---+---+---+---+---+---+
 (price)| 1 | 5 | 8 | 9 | 10| 17| 17| 20|
        +---+---+---+---+---+---+---+---+

We gebruiken een 2D-array dp [m] [n + 1] waarbij n de lengte van de staaf is en m de lengte van de prijsmatrix is. Voor ons voorbeeld hebben we dp [8] [9] nodig . Hier geeft dp [i] [j] de maximale prijs aan door de staaf met lengte j te verkopen. We kunnen de maximale waarde van lengte j als geheel hebben of we hadden de lengte kunnen breken om de winst te maximaliseren.

In het begin zal het voor de 0e kolom niets bijdragen, dus alle waarden als 0 markeren. Dus alle waarden van de 0e kolom zijn 0. Voor dp [0] [1] , wat is de maximale waarde die we kunnen krijgen verkoopstaaf met lengte 1.Het wordt 1.Soortgelijk voor staaf met lengte 2 dp [0] [2] kunnen we 2 (1 + 1) hebben. Dit gaat door tot dp [0] [8] . Dus na de eerste iteratie onze dp [] array ziet eruit.

      +---+---+---+---+---+---+---+---+---+
 (price)| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
        +---+---+---+---+---+---+---+---+---+
  (1) 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 |
        +---+---+---+---+---+---+---+---+---+
  (5) 2 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
  (8) 3 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
  (9) 4 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (10) 5 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (17) 6 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (17) 7 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (20) 8 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+

Voor dp [2] [2] moeten we ons afvragen wat ik het beste kan krijgen als ik de staaf in twee stukken (1,1) breek of de staaf als geheel neem (lengte = 2). We kunnen zien dat als ik de staaf in twee stukken breek, de maximale winst die ik kan maken 2 is en als ik de staaf als geheel heb, ik hem voor 5 kan verkopen. Na de tweede iteratie ziet de dp [] array eruit:

     +---+---+---+---+---+---+---+---+---+
 (price)| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
        +---+---+---+---+---+---+---+---+---+
  (1) 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 |
        +---+---+---+---+---+---+---+---+---+
  (5) 2 | 0 | 1 | 5 | 6 | 10| 11| 15| 16| 20|
        +---+---+---+---+---+---+---+---+---+
  (8) 3 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
  (9) 4 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (10) 5 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (17) 6 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (17) 7 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+
 (20) 8 | 0 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+ 

Dus om dp [i] [j] te berekenen, ziet onze formule er als volgt uit:

if j>=i
    dp[i][j] = Max(dp[i-1][j], price[i]+arr[i][j-i]);
else
    dp[i][j] = dp[i-1][j];

Na de laatste iteratie ziet onze dp [] array eruit

       +---+---+---+---+---+---+---+---+---+
 (price)| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
        +---+---+---+---+---+---+---+---+---+
  (1) 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 |
        +---+---+---+---+---+---+---+---+---+
  (5) 2 | 0 | 1 | 5 | 6 | 10| 11| 15| 16| 20|
        +---+---+---+---+---+---+---+---+---+
  (8) 3 | 0 | 1 | 5 | 8 | 10| 13| 16| 18| 21|
        +---+---+---+---+---+---+---+---+---+
  (9) 4 | 0 | 1 | 5 | 8 | 10| 13| 16| 18| 21|
        +---+---+---+---+---+---+---+---+---+
 (10) 5 | 0 | 1 | 5 | 8 | 10| 13| 16| 18| 21|
        +---+---+---+---+---+---+---+---+---+
 (17) 6 | 0 | 1 | 5 | 8 | 10| 13| 17| 18| 22|
        +---+---+---+---+---+---+---+---+---+
 (17) 7 | 0 | 1 | 5 | 8 | 10| 13| 17| 18| 22|
        +---+---+---+---+---+---+---+---+---+
 (20) 8 | 0 | 1 | 5 | 8 | 10| 13| 17| 18| 22|
        +---+---+---+---+---+---+---+---+---+

We hebben het resultaat op dp [n] [m + 1] .

Implementatie in Java

public int getMaximumPrice(int price[],int n){
        int arr[][] = new int[n][price.length+1];
        
        for(int i=0;i<n;i++){
            for(int j=0;j<price.length+1;j++){
                if(j==0 || i==0)
                    arr[i][j] = 0;
                else if(j>=i){
                    arr[i][j] = Math.max(arr[i-1][j], price[i-1]+arr[i][j-i]);
                }else{
                    arr[i][j] = arr[i-1][j];
                }
            }
        }
        return arr[n-1][price.length];
    }

Tijd Complexiteit

O(n^2)