算法导论——背包

背包，可以简单的理解为**需在一个背包中装下价值最大的东西** 背包主要分为： - 01背包 - 完全背包 - 多重背包 - 混合背包 - 二维背包 - 分组背包 - 依赖背包 - 其他背包 这里主要讲前三种（后面请自行查阅背包九讲） 01背包：指**所有的物品都只有一个**，非0（不拿）即1（拿），故称01背包 01背包思路简单，直接上代码： ```cpp for(int i=1;i<=n;i++) for(int v=m;v>=w[i];v--) if(f[v]<f[v-w[i]]+c[i])f[v]=f[v-w[i]]+c[i]; ``` （此处m为背包容量，w表示花费，c表示价值，f是可容纳最大价值） 时间复杂度：$O \left ( nm \right )$，空间复杂度：$O \left ( m \right )$ 完全背包：指**所有的物品都有无限个**，类似于01背包，但是需要将循环反着写，也就是： ```cpp for(int i=1;i<=n;i++) for(int v=w[i];v<=m;v++) if(f[v]<f[v-w[i]]+c[i])f[v]=f[v-w[i]]+c[i]; ``` 时间复杂度：$O \left ( nm \right )$，空间复杂度：$O \left ( m \right )$ 多重背包：指**所有的物品都有一定的个数**，需要额外的一层循环： ```cpp for(int i=1;i<=n;i++) for(int v=m;v>=w[i];v--) for(int k=0;k<=c[i];k++) if(f[v]<f[v-w[i]*k]+c[i]*k)f[v]=f[v-w[i]*k]+c[i]*k; ``` （注：此处c数组表示物品个数） 时间复杂度：$O \left ( nmc_{max} \right )$，空间复杂度：$O \left ( m \right )$ 总体来说，背包的**时间复杂度偏高，空间复杂度却极低，因此有时需要单调队列、堆、队列等各种优化**，当然，一般情况下用不到这些优化，此处也就不再叙述 背包也属于**NOIP中常考算法之一**（毕竟属于DP），**尤其是普及组**，所以小伙伴们要注意了，背包**并不难，但是难以想到**，因此要多多考虑再选择算法