【解決方法】メモ化されたカットロッド補助出力アルゴリズムの正しい答えを得るにはどうすればよいですか?

[ad_1]

Cut Rod aux アルゴリズムの実装で正しい出力が得られません。Memoized Cut rod aux 関数の実装に Visual Studio 2010 を使用しています….

C++

int max_val=0;

int max(int a, int b)
    {
         return(a>b)?a:b;
    }
int cut_rod_aux(int, int, int);
int cut_rod(int, int);

ほとんどの場合、コードのこのセクションにエラーがあります

C++

int cut_rod_aux(int price[], int n, int r[])
   {
        if(r[n]>=0)
          {
               return r[n];
                cout<<"aux r="<<r<<endl;
          }
        if (n==0)
          {
                max_val=0;
                cout<<"aux max val = 0"<<endl;
          }
        else
         {   /*most probably error area*/
              max_val = 0;
              for(int i=1; i<n;>
              {
                         max_val=max(max_val, price[i]+cut_rod_aux(price, n-i,r));
                         cout<<"aux max val: "<<max_val<<endl;
                  }
          }

       r[n]=max_val;
       return max_val;
   }
   int cut_rod(int price[], int n)
   {
        int *r = new int[n];
        for(int i=0; i<n;>                {
                r[i]=0;
                cout<<"i="<<i<<" r="<<r[i]<<endl;
            }
       return cut_rod_aux(price,n,r);
   }
   int _tmain(int argc, _TCHAR* argv[])
   {
          int arr[]={1, 5, 8, 9, 10, 17, 17, 20};
           cout<<"output "<<cut_rod(arr, 8)<<endl;
          /*output should be 22, as per coreman book*/
       return 0;
   }

私が試したこと：

正しい出力は 22 であるはずですが、代わりに 20…

解決策 1
解決策 2

解決策 1

できるだけ早くデバッガの使用方法を習得する必要があります。コードが何を行っているかを推測するのではなく、コードの実行を確認し、期待どおりに動作することを確認します。

デバッガーを使用すると、実行を 1 行ずつ追跡し、変数を調べることができ、期待どおりの動作を停止するポイントがあることがわかります。
Visual Studio 2010 でのデバッグの習得 – 初心者向けガイド[^]
http://docs.oracle.com/javase/7/docs/technotes/tools/windows/jdb.html[^]
https://www.jetbrains.com/idea/help/debugging-your-first-java-application.html[^]

この行は控えめに言っても奇妙です。コードの欠落？

for(int i=1; i<n;>

解決策 2

この問題は、動的計画法の棒を切る問題に似ています。解決する方法は次のとおりです。

方法 1

さまざまな部品のすべての構成を生成し、最適な解決策を選択します。与えられた解は、指数関数的な時間の複雑さです。
C++言語での解決策は次のとおりです。

#include<bits/stdc++.h>
using namespace std;
int getMax(vector<int> &cost, int ide, int n)
{
    if (ide == 0) { // base case
        return n * cost[0];
    }
    // for any size we have two choices whether we will make a cut or not.
    int nt = getMax(cost,ide- 1,n); 
    int cut = INT_MIN;
    int length_of_rod = ide + 1;
 
    if (length_of_rod <= n)
    {
        // Recursive call to get output for smaller tasks.
        cut = cost[ide] + getMax(cost,ide,n - length_of_rod); 
    }
     // Returns maximum two solutions after making a cut or not.
    return max(nt, cut);
}


int main()
{
     // takes size of the rod
    int n;
    cin>>n;
    // array to store cost of each size of the rod
    vector<int> arr(n); // arrays to store cost of each size of the rod
    for(int i=0;i<n;i++)
          cin>>arr[i];
    cout<<getMax(arr,n-1,n); // function call to getMaximum cost.
    return 0;
}

方法 2

この方法では、問題に部分構造が重複していることを確認できます。メモ化を使用して、重複する再帰呼び出しを減らします。 C ++プログラミング言語での解決策について説明しましょう。

#include<bits/stdc++.h>
using namespace std;
int getMax(vector<int> &cost, int ide, int n,vector<vector<int>> &dp)
{
     // Base case of the problem
    if (ide == 0) {
        return n * cost[0];
    }
     // If the value is already for any substructure, it directs returns its value.
    if(dp[ide][n]!=-1)
         return dp[ide][n];
    
    int nt = getMax(cost,ide- 1,n,dp); 
    int cut = INT_MIN;
    int length_of_rod = ide + 1;
 
    if (length_of_rod <= n)
    {   
        // Recursive call to get output for smaller tasks   
        cut = cost[ide] + getMax(cost,ide,n - length_of_rod,dp);
     }
    // Here we have used memoization to store and return maximum two solutions after making a cut or not.
    return dp[ide][n]=max(nt,cut);

}
int main()
{
    // Takes size of the rod
    int n;
    cin>>n;
    // Array to store cost of each size of the rod
    vector<int> arr(n); 
    for(int i=0;i<n;i++)
         cin>>arr[i];
    vector<vector<int>> dp(n,vector<int>(n+1,-1)); 
    // Function call to get maximum cost.
    cout<<getMax(arr,n-1,n,dp); 
    return 0;
}