这两天c++的习题开始不考察c++了，开始考察动态规划问题，唉，没学过动态规划算法来编这题目真是一把辛酸泪，下面给出题目（题目来源：郭玮老师的mooc）
2:Charm Bracelet
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
Bessie has gone to the mall’s jewelry store and spies a charm bracelet. Of course, she’d like to fill it with the best charms possible from the N(1 ≤ N≤ 3,402) available charms. Each charm iin the supplied list has a weight Wi(1 ≤ Wi≤ 400), a ‘desirability’ factor Di(1 ≤ Di≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M(1 ≤ M≤ 12,880).
Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.
输入
Line 1: Two space-separated integers: N and M
Lines 2…N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di
输出
Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints
样例输入
4 6
1 4
2 6
3 12
2 7
样例输出
23
看上去这题确实不难，真正的题目就是给定总重量m，求最大的desirability。然后我一下子想到只要遍历一下所有情况，然后取出weight满足的情况中desirability最大的即可，贴出我写的代码：
1#include <iostream> 2#include <cstring> 3#define MAX 3402 4using namespace std; 5 6class charm; 7int combine_decrease(int m , charm* arr, int start, int* result, int count, const int NUM); 8 9class charm 10{ 11public: 12 int w; 13 int d; 14}; 15 16 17int main (void) 18{ 19 int n; 20 int m; 21 int i; 22 int j ; 23 int max_desir = 0; 24 int temp = 0; 25 charm charm_list[MAX] ; 26 int result[MAX] ; 27 cin>>n>>m; 28 for(i=0;i<n;i++){ 29 cin>>charm_list[i].w>>charm_list[i].d; 30 }//have stored the charm; 31 for(i = 1;i <= n; ++i){ 32 temp = combine_decrease(m,charm_list , n , result , i , i ); 33 if (temp >= max_desir) 34 max_desir = temp; 35 } 36 cout<<max_desir; 37 38} 39 40 41//arr涓哄師濮嬫暟缁? 42//start涓洪亶鍘嗚捣濮嬩綅缃? 43//result淇濆瓨缁撴灉锛屼负涓€缁存暟缁? 44//count涓簉esult鏁扮粍鐨勭储寮曞€硷紝璧疯緟鍔╀綔鐢? 45//NUM涓鸿閫夊彇鐨勫厓绱犱釜鏁? 46int combine_decrease(int m, charm* arr, int start, int* result, int count, const int NUM) 47{ 48 int i; 49 int sum = 0; 50 int temp = 0; 51 int temp_weight = 0; 52 for (i = start; i >=count; i--) 53 { 54 result[count - 1] = i - 1; 55 if (count > 1) 56 { 57 temp = combine_decrease(m,arr, i - 1, result, count - 1, NUM); 58 if(temp >= sum){ 59 sum = temp; 60 } 61 temp = 0; 62 } 63 else 64 { 65 int j; 66 for (j = NUM - 1; j >=0; j--){ 67 temp_weight +=arr[result[j]].w; 68 temp += arr[result[j]].d; 69 //printf("%d ",arr[result[j]].d);; 70 if(temp_weight > m) break; 71 } 72 //cout<<endl; 73 //cout<<"desire:"<<temp<<"weight:"<<temp_weight<<endl; 74 if(temp>=sum && temp_weight <= m) 75 sum = temp; 76 //cout<<"sum:"<<sum<<endl; 77 temp = 0; 78 temp_weight = 0; 79 } 80 } 81 return sum; 82}
答案确实是做出来了，应该也是对的，然后提交后出现**“超时”**，唉想想也是，遍历所有情况，想想都害怕，还用递归来实现，机子肯定要爆掉。没办法实在想不出，上网查资料。
一查就查到了，这是经典的01背包问题，也就是经典的动态规划求解问题：
代码来源https://blog.csdn.net/qingboda110/article/details/51050299
1#include<stdio.h> 2int W[3500]; 3int D[3500]; 4int f[13000]; 5int main(){ 6 int ans,max,n,i,j; 7 scanf("%d",&n); 8 scanf("%d",&max); 9 for(i=0;i<n;i++){ 10 scanf("%d",&W[i]); 11 scanf("%d",&D[i]); 12 } 13 for(i=0;i<n;i++){ 14 for(j=max;j>0;j--){ 15 if(j>=W[i]&&f[j]<f[j-W[i]]+D[i]) 16 f[j]=f[j-W[i]]+D[i]; 17 } 18 } 19 ans=0; 20 for(i=0;i<=max;i++){ 21 if(f[i]>ans) 22 ans=f[i]; 23 } 24 printf("%d\n",ans); 25 return 0; 26} 27
一提交果然成功，但是看着代码依然无法理解，继续查资料，发现了这篇博文，讲的很好，看了半小时终于搞懂了，01背包问题，给出博文地址：https://www.cnblogs.com/wujing-hubei/p/6376218.html?utm_source=tuicool&utm_medium=referral
动态规划的思路，还是用小问题的解决去解决大问题，然后关键就在于找到大问题到小问题的简化关系：
在此谢过博主的帮助了。