c++ - 计算杆的最大总价，切割具有唯一长度值

Question

切杆问题(有一根长度为n的杆，其中n > 0，n为整数，我们想将它切成整数长度的多段，使得总价最大化)，p是列表价格，n是杆的长度。我要切杆，为了得到最大的价格，同时还要保证长度是唯一的，即如果已经切了一段length = 3，就不能再切一段length = 3 .

例如 vector p = {1, 5, 8, 9, 10, 12, 17, 20};给我最高价格:21，长度为:2、3、3。如前所述，不应该有双 3。所以结果应该是 20，长度是 8 而不是 2,3,3

我如何修改我的代码，并保持时间复杂度 O(n^2) 谢谢。

int n = 8;
vector<int> p = {1,5,8,9,10,12,17,20};

void cut_rod(vector<int>& p, int n){

    int r[n+1];
    int s[n+1];
    r[0] = 0;

    for (int j = 1; j<=n; j++){
        int q = INT_MIN;
        for (int i = 1; i <= j; i++){
            if(q < p[i-1] + r[j-i]){

                q = p[i-1] + r[j-i];
                s[j] = i;
            }
        }
        r[j] = q;
    }
    return r[n];

}

Answer 1

当您存储给定长度的片段时，您可以使用 n + 1 x n + 1 矩阵。通过这种方式，您可以在恒定时间内检查是否有相同大小的片段，并且复制一行会花费线性时间，因此总的来说复杂度仍然是 O(n^2)，但现在您的空间复杂度是 O(n^2)。

我修改了下面geeksforgeeks的代码。

// A Dynamic Programming solution for Rod cutting problem
#include<stdio.h>
#include<limits.h>
using namespace std;
// A utility function to get the maximum of two integers
int max(int a, int b) { return (a > b)? a : b;}

/* Returns the best obtainable price for a rod of length n and
price[] as prices of different pieces */
int cutRod(int price[], int n)
{
   int pieces[n+1][n+1];    
   int val[n+1];
   val[0] = 0;
   int i, j;

   // Build the table val[] in bottom up manner and return the last entry
   // from the table
   for (i = 1; i<=n; i++)
   {
       int max_val = INT_MIN, ind = -1;
       for (j = 1; j <= i; j++) {
           if (max_val < price[j - 1] + val[i-j]) {
               if (pieces[i-j][j] != 1) {                   
                   max_val = price[j - 1] + val[i-j];
                   ind = j;
               }
           }
       }
       val[i] = max_val;
       for (int k = 0; k <= n; ++k) { // Copy the pieces
           pieces[i][k] = pieces[i-ind][k];
       }
       pieces[i][ind] = 1; // Add the piece of length ind (which is the max j)
   }
   return val[n];
}

/* Driver program to test above functions */
int main()
{
    int arr[] = {1,5,8,9,10,12,17,20};
    int size = sizeof(arr)/sizeof(arr[0]);
    printf("Maximum Obtainable Value is %dn", cutRod(arr, size));
    getchar();
    return 0;
}

DP 算法在数组 val 的第 i 个位置(从 0 到 n)保存长度为 i 的杆的最高价格。我们将长度为 i 的杆的切割保存在 pieces[i] 中，这是一个从 0 到 n 的数组，如果我们在位置 j 处有 1，这意味着要获得最大值 val[i] 你必须有一个 piece长度 j。现在，DP 算法对某个长度 i 进行长度 j 的切割，并计算长度 j 的价格与已经计算出的长度 i-j 的剩余部分的最大价格之和。这个总和对于某些 j 将具有最大值，这意味着将有一些 j price[j - 1] + val[i-j] 将是最大值(其中 j 不是已经存在的切割)。所以现在对于长度 i，我们有一个长度为 j 的片段和长度为 i - j 的片段，我们保存在片段 [i - j] 中。现在要获得 pieces[i] 我们必须复制 pieces[i - j] 并添加长度为 j 的片段。

你可以这样得到碎片的长度

for (int i = 0; i <= n; ++i) 
    if (pieces[n][i] == 1)  cout << i << ' ';