[ad_1]
Cut Rod aux アルゴリズムの実装で正しい出力が得られません。Memoized Cut rod aux 関数の実装に Visual Studio 2010 を使用しています….
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);
ほとんどの場合、コードのこのセクションにエラーがあります
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
できるだけ早くデバッガの使用方法を習得する必要があります。 コードが何を行っているかを推測するのではなく、コードの実行を確認し、期待どおりに動作することを確認します。
デバッガーを使用すると、実行を 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; }
[ad_2]
コメント