假定公司出售一段長度為i英寸的鋼條的利潤為Pi,那么現有一根N英寸的鋼條該如何切割才能利潤大,大為多少。

#include#includeusing namespace std;
void mycut_roin(const int p[], int length, int n, int optim_income[], int optim_solution[]);
void show_array(int arr[], int n);
int main()
{const int length = 10;
int p[length+1] = {0,1,5,8,9,10,17,17,20,24,30 };
int n;
cin >>n;
int* optim_income(new int[n + 1]);
int* optim_solution(new int[n + 1]);
mycut_roin(p, length, n, optim_income, optim_solution);
cout<< "The optimal income: "<< optim_income[n]<< endl;
while (n >0)
{cout<< optim_solution[n]<< ' ';
n -= optim_solution[n];
}
delete[] optim_income;
delete[] optim_solution;
return 0;
}
void mycut_roin(const int p[], int length, int n, int optim_income[], int optim_solution[])
{optim_income[0] = optim_solution[0] = 0;
for (int i = 1; i<= n; i++)
{int max_income = INT_MIN;
for (int j = 1; j<= i; j++)
{ int pval = (j >= length) ? p[length] : p[j];
if (pval + optim_income[i - j] >max_income)
{ max_income = pval + optim_income[i - j];
optim_solution[i] = j;
}
}
optim_income[i] = max_income;
}
show_array(optim_income, n + 1);
show_array(optim_solution, n + 1);
}
void show_array(int arr[], int n)
{for (int i = 0; i< n; i++)
{cout.width(4);
cout<< arr[i]<< ' ';
}
cout<< endl;
}
你是否還在尋找穩定的海外服務器提供商?創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源,準確流量調度確保服務器高可用性,企業級服務器適合批量采購,新人活動首月15元起,快前往官網查看詳情吧
新聞標題:C++實現——動態規劃法(切割鋼條問題)-創新互聯
轉載來于:http://www.js-pz168.com/article44/dhdgee.html
成都網站建設公司_創新互聯,為您提供網站制作、企業網站制作、軟件開發、網站導航、Google、自適應網站
聲明:本網站發布的內容(圖片、視頻和文字)以用戶投稿、用戶轉載內容為主,如果涉及侵權請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網站立場,如需處理請聯系客服。電話:028-86922220;郵箱:631063699@qq.com。內容未經允許不得轉載,或轉載時需注明來源: 創新互聯