题目：有n个重量和价值分别为wi,vi的物品。从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。
题目的限制条件：
1） 1<=n<=100
2) 1<=wi,vi<=100
3) 1<=W<=10000
样例输入：
n = 4
(w,v) = { (2,3), (1,2), (3,4), (2,2) }
W = 5
解析：该书给出的思路是先用最朴素的方法，针对每个物品是否放入背包进行搜索试试。代码如下：
#include<iostream> #include<algorithm> #include<string.h> using namespace std; const int maxn = 110; typedef long long ll; int n,w1,w[maxn],v[maxn]; //从第i个物品开始挑选总重小于j的部分 ll solve(int i,int j) { int res; if(i==n) res = 0; //已经没有剩余的物品了 else if(j<w[i]) res = solve(i+1,j); //无法挑选这个物品 else res = max(solve(i+1,j),solve(i+1,j-w[i])+v[i]); //挑选和不挑选都要尝试一遍 return res; } int main() { ios::sync_with_stdio(false); cin>>n; for(int i=0;i<n;i++) cin>>w[i]>>v[i]; cin>>w1; cout<<solve(0,w1)<<endl; return 0; }该算法的最坏时间复杂度是,可以知道，当n取的稍微大些的时候，比如50，那你的程序铁定TLE。这时你要重新思考一种解决方案，有没有一种降低复杂度的实现方案，能使得复杂度降低？
没错，记忆化搜索，这种能避免大量子状态的重新计算，换言之，已经计算过的状态，下次递归调用遇到的时候直接返回调用处函数的值，不需要再次计算。
记忆化代码能使问题的复杂度降低到。参数的组合不过nW种，所有复杂度为。
代码如下：
#include<iostream> #include<algorithm> #include<string.h> using namespace std; const int maxn = 110; typedef long long ll; int n,w1,w[maxn],v[maxn]; ll dp[maxn][maxn]; //从第i个物品开始挑选总重小于j的部分 ll solve(int i,int j) { if(dp[i][j] != -1) return dp[i][j]; int res; if(i==n) res = 0; //已经没有剩余的物品了 else if(j<w[i]) res = solve(i+1,j); //无法挑选这个物品 else res = max(solve(i+1,j),solve(i+1,j-w[i])+v[i]); //挑选和不挑选都要尝试一遍 return dp[i][j] = res; } int main() { ios::sync_with_stdio(false); memset(dp,-1,sizeof(dp)); //dp数组初始化为-1 cin>>n; for(int i=0;i<n;i++) cin>>w[i]>>v[i]; cin>>w1; cout<<solve(0,w1)<<endl; return 0; }这时，一位大佬闪亮登场，他诙谐的说，这么简单的题一个递推式就解决了！是不是有点想打他。好了，不闹了，还是好好来写代码吧。。。。
我们先找出递推关系式子：
（其他） 上面一个是成立的时候的表达式的值（排版上由于自己还未完全能清楚，所以只能这样了，呜呜呜呜~~~）
从前i个物品选出总重量不超过j的物品时总价值的最大值
初始化：
代码如下：
#include<iostream> #include<algorithm> #include<string.h> using namespace std; const int maxn = 110; typedef long long ll; ll w[maxn],v[maxn],n,W; ll dp[maxn][maxn]; int main() { ios::sync_with_stdio(false); memset(dp,0,sizeof(dp)); //这一步我是偷巧了，其实让dp[0][j] = 0就可以了 cin>>n; for(int i=0;i<n;i++) cin>>w[i]>>v[i]; cin>>W; for(int i=0;i<n;i++) { for(int j=0;j<=W;j++) { if(j<w[i]) //这个物品装不下 dp[i+1][j] = dp[i][j]; else //能装下 dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i]); } } cout<<dp[n][W]<<endl; return 0; }一维滑的滚动数组先不解释了，新手先把这些给消化，天也黑了，以后补上！
