程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> C++處理一個動態規劃的問題,處理動態規劃

C++處理一個動態規劃的問題,處理動態規劃

編輯:C++入門知識

C++處理一個動態規劃的問題,處理動態規劃


嗯哼,別人問的問題,看的我也頭暈,百度了一下動態規劃,看了看才想起來該怎麼做,今天寫了寫代碼,實現了~

要求是遞歸,動態規劃,想了想這種方法也是最簡單的~

所謂動態規劃:把多階段過程轉化為一系列單階段問題,利用各階段之間的關系,逐個求解。動態規劃算法通常用於求解具有某種最優性質的問題。在這類問題中,可能會有許多可行解。每一個解都對應於一個值,我們希望找到具有最優值的解。動態規劃算法與分治法類似,其基本思想也是將待求解問題分解成若干個子問題,先求解子問題,然後從這些子問題的解得到原問題的解。與分治法不同的是,適合於用動態規劃求解的問題,經分解得到子問題往往不是互相獨立的。若用分治法來解這類問題,則分解得到的子問題數目太多,有些子問題被重復計算了很多次。如果我們能夠保存已解決的子問題的答案,而在需要時再找出已求得的答案,這樣就可以避免大量的重復計算,節省時間。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以後是否被用到,只要它被計算過,就將其結果填入表中。這就是動態規劃法的基本思路。(摘自百科)(時間復雜度為一個多項式的復雜度)

背包問題(Knapsack problem)是一種組合優化的NP完全問題。問題可以描述為:給定一組物品,每種物品都有自己的重量和價格,在限定的總重量內,我們如何選擇,才能使得物品的總價格最高。問題的名稱來源於如何選擇最合適的物品放置於給定背包中。

 

題目如截圖:

 

 

解題思路:

n代表面值

n為1,直接看是否可以整除;

n>1,看在沒有第n個面值的時候多少,然後看有1個、2個....j/n個面值為n的時候需要幾枚硬幣,取最小值

將這些直接存在數組中,然後去數組裡的最小值

代碼:

 1 #include"header_file.h"
 2 using namespace std;
 3 
 4 int coin_num(vector<int> T,int i,int j)
 5 {
 6     if(i==1)
 7     {
 8         if(j%T[0]==0)
 9         {
10             return j/T[0];
11         }
12         else
13         {
14             return 9999;
15         }
16     }
17     else
18     {
19         int min;
20         min=coin_num(T,i-1,j);
21         int temp;
22         temp=j/T[i-1];
23         for(int m=0;m<=temp;m++)
24         {
25             if(min>(m+coin_num(T,i-1,j-m*T[i-1])))
26                 min=m+coin_num(T,i-1,j-m*T[i-1]);
27             
28         }
29         return min;
30     }
31 }
32 
33 vector<int> all_num(vector<int> T,int j)
34 {
35     vector<int> v;
36     for(int i=0;i<T.size();i++)
37         v.push_back(coin_num(T,i+1,j));
38 //    for(int i=0;i<T.size();i++)    //use for test
39 //        cout<<v[i]<<" ";
40         //v.push_back(coin_num(T,i+1,j));
41     return v;
42 }
43 
44 int find_min(vector<int> v)
45 {
46     int min=0;
47     for(int i=1;i<v.size();i++)
48     {
49         if(v[min]>v[i])
50             min=i;
51     }
52     return v[min];
53 }
54 
55 int main(void)
56 {
57     int n;
58     cout<<"input n:";
59     cin>>n;
60     
61     vector<int> T;
62     for(int i=0;i<n;i++)
63     {
64         int temp;
65         cin>>temp;
66         T.push_back(temp);
67     }
68     
69     int j;
70     cout<<"input j:";
71     cin>>j;
72     
73     vector<int> v;
74     v=all_num(T,j);
75     int min;
76     min=find_min(v);
77     cout<<"min:"<<min<<endl;
78 }

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved