目录
题目最基本的想法
思想
引申
解决方案解决方案代码 其他解法
==memset原理== 题目 最基本的想法
#includeusing namespace std;int n,W;const int MAX_SIZE=100;int w[MAX_SIZE+1],v[MAX_SIZE+1];void solve();int rec(int,int);int main(){ cin >> n >> W; for(int i=0;i> w[i] >> v[i]; } solve();}void solve(){ cout << rec(0,W);}int rec(int i,int j){//i表示从第几件物品开始取，j表示能取的容量还有多少 int res;//每一层都会有一个叫做res的变量,用于记录当前层数下的背包价值 if(i==n){//物品的编号是从0~n-1的，这里==n表示已经取到头了 res=0; }else if(j
思想
这种解法的思想就是
要知道在容量为W，可选物品为0~n-1的情况最大价值是多少
我们就去寻找
在容量为W，可选物品为1~n-1的情况最大价值是多少（不拿第1件物品之后）在容量为W-j，可选物品为1~n-1的情况最大价值是多少（拿第一件物品之后）
这样递归的结构一目了然
然后我们再把当前层的最优解存在res里，层层返回，就得到了最终的最优解
输出即可
这里我们还可以发现，递归都是从复杂问题入手，逐渐变成简单问题，且具有相同子结构~
引申
可能已经有读者已经发现了，上面的形式与二叉树相似，因此我们可以说它的复杂度为n2
，因此，当n比较大的时候，翻车是必然的。除此之外还可能会出现重复计算的问题。
解决方案
因此，我们可以用一个数组把内容记录下来，这样用到的时候直接调用即可。
解决方案代码
#includeusing namespace std;int n,W;const int MAX_SIZE=100;int w[MAX_SIZE+1],v[MAX_SIZE+1];int record[110][1010];// todo 用于记录每次res的值void solve();int rec(int,int);int main(){ cin >> n >> W; for(int i=0;i> w[i] >> v[i]; } solve(); system("pause"); return 0;}void solve(){ cout << rec(0,W);}int rec(int i,int j){ if(record[i][j]==0){ int res; if(i==n){ res=0; }else if(j
超时的问题迎刃而解~
其他解法
我们可不可以不利用递归写呢？答案是可以
复杂度也是n*W，其实和上文思路是一样的，但是这里我们用两个for循环
假设当前背包容量为V，物品的价值为val，体积为wgt，我们要考虑的就是这个物品要不要拿？那么怎么进行比较呢，我们可以用背包容量为V-wgt时的价值+val（相当于拿这个物体），与现在容量为V时的价值进行比较（也就相当于不拿这个物品），如果前者的价值更高，那么就选择拿这个物体，如果不拿这个物体时的价值高，那么就不拿这个物体。
这个想法有点绕，笔者拙笨，不能清楚的讲述出来，更多内容可参见大佬的背包九讲。
#include#includeusing namespace std;int n,W;//n表示物品数量,W表示背包容量struct thing{ int _w,_v; thing(int w,int v){ this->_w=w; this->_v=v; } thing(){};};int main(){cin >> n >> W; thing T[110];for(int i=0;i> T[i]._w >> T[i]._v;} int w[1010]={0}; //首先肯定是双重循环控制，外层循环控制是哪个物品 //内层循环控制背包当前容量 for(int i=0;i=0;j--){//这里的容量就是从W开始计算的，并不用考虑W-1 int v=j-T[i]._w; if(v>=0){ w[j]=max(w[j],w[v]+T[i]._v); } } } //迭代完成，查看最终结果 cout << w[W] << endl; return 0;}// todo 我们的思路是
顺带一提，使用包含在cstring中的memset(array,val,sizeof(array))函数可以快速初始化高维数组的值为指定的值(val)。包含的头文件不能写成string，必须是cstring。
注意！！！不能将数组的值设为1等其他值
可以设置成0或-1
memset原理 memset修改的是内存，一次直接修改一个字节（8位），而我们的数组是32位int型的，如果设置成1的话用2进制来表示是00000001，一共表示4次，得到的值换算成10进制就是
那么为什么可以刷成0或-1呢？
0自然不必解释00000000
-1就涉及到补码的知识了
在计算机组成原理中我们学过原码反码补码
我们知道-1的原码是符号位加上真值的绝对值，因此-1的原码是10000001，将-1的原码转换为反码，方法是符号位保持不变，其余按位取反，因此-1的反码是11111110，最后将反码转换为补码，末位+1，符号位保持不变，得到-1的补码11111111，因此我们可以利用memset快速将数组赋值成-1~