dynamic-programming
Taglio dell'asta

Tagliare la barra per ottenere il massimo profitto

Data una verga di lunghezza n pollici e una serie di lunghezza m di prezzi che contiene i prezzi di tutti i pezzi di dimensioni inferiori a n. Dobbiamo trovare il massimo valore ottenibile tagliando la canna e vendendo i pezzi. Ad esempio, se la lunghezza dell'asta è 8 e i valori di pezzi diversi sono dati come segue, allora il valore massimo ottenibile è 22 .

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

Useremo un array 2D dp [m] [n + 1] dove n è la lunghezza dell'asta e m è la lunghezza dell'array del prezzo. Per il nostro esempio, avremo bisogno di dp [8] [9] . Qui dp [i] [j] indicherà il prezzo massimo vendendo la verga di lunghezza j.Possiamo avere il valore massimo della lunghezza j nel suo insieme o avremmo potuto spezzare la lunghezza per massimizzare il profitto.

All'inizio, per la 0ª colonna, non contribuirà a nulla, quindi contrassegnerà tutti i valori come 0. Quindi tutti i valori della 0a colonna saranno 0. Per dp [0] [1] , qual è il valore massimo che possiamo ottenere da asta di vendita di lunghezza 1. Sarà 1. Similmente per asta di lunghezza 2 dp [0] [2] possiamo avere 2 (1 + 1). Questo continua fino a dp [0] [8] . Quindi dopo la prima iterazione apparirà il nostro array dp [].

      +---+---+---+---+---+---+---+---+---+
 (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 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+

Per dp [2] [2] dobbiamo chiederci che cosa è il meglio che posso ottenere se rompo la verga in due pezzi (1,1) o prendendo l'asta nel suo insieme (lunghezza = 2). Possiamo vedere che se rompo la canna in due pezzi il massimo guadagno che posso fare è 2 e se ho la canna nel suo insieme posso venderla per 5. Dopo la seconda iterazione la matrice dp [] avrà il seguente aspetto:

     +---+---+---+---+---+---+---+---+---+
 (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 |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+ 

Quindi per calcolare dp [i] [j] la nostra formula sarà simile a:

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];

Dopo l'ultima iterazione apparirà il nostro array dp []

       +---+---+---+---+---+---+---+---+---+
 (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|
        +---+---+---+---+---+---+---+---+---+

Avremo il risultato a dp [n] [m + 1] .

Implementazione 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];
    }

Complessità del tempo

O(n^2)