c++ - 我如何使用递归获取 Rod Cut 中的 Rod 尺寸？

Question

我想在杆 ct 问题中获得最大 yield 的杆尺寸。假设有 4 根杆。

1 = 5
2 = 4
3 = 3
4 = 10

在这种情况下，最大收入将由 1,1,1,1 产生，即 20。我获得了最大的收入，但我如何获得杆的尺寸这是代码。

#include<iostream>

using namespace std;

int Rod_Cut(int *,int);
int main()
{
    const int n=5;
    int arr[n]={0,5,4,3,10};
    int size[n]={0};


    cout<<Rod_Cut(arr,n)<<endl;


}

int Rod_Cut(int *arr, int n)
{
    if(n==0)
    {
        return 0;
    }

    int q=0;

    for(int i=1;i<n;i++)
    {

        q=max(q,arr[i]+Rod_Cut(arr,n-i));


    }

    return q;
}

Answer 1

这是一种方法:

您需要返回每次计算中使用的序列。如果新值比您目前拥有的更好，则必须保存新的“最佳”序列。最后，您返回找到的最佳序列。

该提案不是最优的(例如性能)，但也许它会给您一些想法。然后您可以优化代码以获得更好的性能。

祝你好运。

int Rod_Cut(int *,int, vector<int>&);
int main()
{
    const int n=5;
    int arr[n]={0,5,8,3,10};
    int size[n]={0};

    vector<int> v;  // Create vector for the best sequence
    cout<<Rod_Cut(arr,n,v)<<endl;

    // Print the best sequence
    for(auto e : v)
    {
        cout << e << " ";
    }


}

int Rod_Cut(int *arr, int n, vector<int>& v)
{
    if(n==0)
    {
        return 0;
    }

    int q=0;

    vector<int> t;        // Temp vector for next call
    vector<int> st;       // The best sequence found at this level
    for(int i=1;i<n;i++)
    {
        int temp = arr[i]+Rod_Cut(arr,n-i,t);
        if (temp > q)
        {
            // A new better sequence has been found

            st.clear();        // clear the former best sequence
            for(auto e : t)    // add the new best sequence
            {
                st.push_back(e);
            }
            st.push_back(i);   // add i used at this level
            q = temp;
        }

        t.clear();   // Prepare for next call
    }

    // Copy the best sequence to the returned vector
    for (auto e : st)
    {
        v.push_back(e);
    }

    return q;
}