C++处理一个动态规划的问题

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

嗯哼，别人问的问题，看的我也头晕，百度了一下动态规划，看了看才想起来该怎么做，今天写了写代码，实现了~

要求是递归，动态规划，想了想这种方法也是最简单的~

所谓动态规划：把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。（摘自百科）（时间复杂度为一个多项式的复杂度）

背包问题(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 }