关键词：
01背包
有一个体积为V的背包，有n个物品，每个物品都有体积vi和价值wi，在背包体积范围内，求能桌下的最大价值。
这个问题中每个物品只能用一次。
设dp[i][j]表示用前i个物品装体积为j的背包。
那么第i个物品要么装要么不装：
1、如果不装，第i个物品和没有一样，dp[i][j]=dp[i-1][j]
2、如果装，减去第i个物品的体积，加上第i个物品的价值，那么它还是和没有一样。。dp[i][j]=dp[i-1][j-v[i]]+w[i];
我们只需取这两种方案的最大值，就算是解决了。dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
时间复杂度是O(V*M),空间也是O(V*M)
其实空间可以优化
注意观察，可以发现每个状态dp[i][j]之和dp[i-1][]有关，什么i-2,i-3都没用了
我们试着开一个一维的数组dp[M];
一维难道不会覆盖掉原来的值么？
会的，但我们优先覆盖不用的值。怎么说呢？就是我们每次只会用比j小的地方的值，比j大的地方是不用到的，所以我们只要j从后往前枚举，就不会冲突了。
dp[j]=max(dp[j],dp[j-v[i]]+w[i]) [j=N->v[i]]
for（int i= 1； i <= n; i++)
for (int j = m; j >= w[i]; j--)
dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
完全背包
完全背包就是每种物品有无限个的背包
这个时候我们的状态转移方程可以这么写：dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+w[i]);
看起来好像没区别啊？！
真的么？
仔细看看，i-1变成了i
也就是说，选择了第i个物品后，并不是转到i-1，因为每个物品有无限个，所以还是转到了i
状压一下，就是
dp[j]=max(dp[j],dp[j-v[i]]+w[i]) 【j=v[i]->N】
唯一的区别就是j枚举的方向反了过来
for（int i= 1； i<= n; i++)
for (int j = w[i]; j <= m; j++)
dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
动态规划完全背包(代码片段)
完全背包与01背包的区别就是01背包只有一次，而完全背包有无限我的01背包完全背包 dp[i-1][j-k*weight[i]]+k*value[i] 经历了01背包，那么前面这个式子就很好理解了，k就代表无限个。照例，先来一份最朴实无华的递推：int... 查看详情
01背包与完全背包（dp复习）(代码片段)
01背包和完全背包都是dp入门的经典，我的dp学的十分的水，借此更新博客的机会回顾一下01背包：给定总容量为maxv的背包，有n件物品，第i件物品的的体积为w[i],价值为v[i],问如何选取才能是背包内的物品价值总和最大。stdin：5123... 查看详情
01背包完全背包多重背包分组背包总结
文章目录一、01背包问题二、完全背包问题三、多重背包问题四、分组背包一、01背包问题n个物品，每个物品的重量是，价值是，背包的容量是若每个物品最多只能装一个，且不能超过背包容... 查看详情
背包问题（01背包，完全背包，多重背包）
...http://www.cnblogs.com/daoluanxiaozi/archive/2012/05/06/2486105.html 背包问题，经典有背包九讲。01背包 不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些... 查看详情
01背包，完全背包，多重背包，混合背包
详见大牛背包九讲(下载地址：http://pan.baidu.com/s/1b9edXW)1//Class->物品种类，val->价值，room->所占空间，num->物品数量，Room->背包容量23#include<stdio.h>4constintmaxn=1e6;56intbag[maxn];7intRoom;89voidzero_one_bag( 查看详情
动态规划之背包问题-01背包+完全背包+多重背包(代码片段)
01背包有n种不同的物品，每种物品分别有各自的体积v[i]，价值 w[i] 现给一个容量为V的背包，问这个背包最多可装下多少价值的物品。1for(inti=1;i<=n;i++)2for(intj=V;j>=v[i];j--)3dp[j]=max(dp[j],dp[j-v[i]]+w[i]);//dp[V]为所求完全背包0... 查看详情
01背包完全背包多重背包
参考（都有些错误）：https://github.com/guanjunjian/Interview-Summary/blob/master/notes/algorithms/%E7%BB%8F%E5%85%B8%E7%AE%97%E6%B3%95/01%E8%83%8C%E5%8C%85.mdhttps://blog.csdn.net/na_beginning/article/details/6 查看详情
动态规划_01背包_完全背包_多重背包_分组背包(代码片段)
目录动态规划问题结题思路：模板题链接：01背包思路：代码：完全背包思路:代码多重背包思路：代码：组合背包思路：代码：动态规划问题结题思路：模板题链接：01背包模板题完全背包... 查看详情
动态规划背包问题01背包完全背包多重背包
一、01背包有N件物品和一个容量为V的背包。第i件物品的价格（即体积，下同）是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。这是最基础的背包问题，总的来说就... 查看详情
#1043:完全背包
与01背包区别是：need[i]可以重复importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ //用一维数组实现 Scannersc=newScanner(System.in); intn,m; n=sc.nextInt(); m=sc.nextInt(); intneed[]=newint[n]; intval 查看详情
背包0-1背包与完全背包一维数组实现(代码片段)
背包问题很经典了，《背包问题九讲》讲的非常详细，建议看一看。在这里，我想给出0-1背包和完全背包压缩空间后的实现，即只要一维数组。0-1背包，与完全背包仅仅只是内循环的次序不同，故而代码基本相同。希望可以帮的... 查看详情
01完全多重背包模板
背包问题：背包总容量为W，有n件重量为weight[i],权值为value[i]的物品1、01背包：这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。1voidZeroOnePack(intweight,intvalue)2{3for(intw=W;w>=weight;w--)4dp[w]=max(dp[w-weight]+value,... 查看详情
01背包+完全背包+多重背包+单调队列(代码片段)
01背包代码：逆序更新intn,m,f[105][N],dp[N];voidfun1()for(inti=1;i<=n;i++)//物品ifor(intj=1;j<=m;j++)//容量jif(j<w[i])f[i][j]=f[i-1][j];elsef[i][j]=max(f[i-1] 查看详情
算法----01背包问题和完全背包问题leetcode系列问题题解(代码片段)
背包问题1、01背包入门1.1二维背包1.2一维背包2、01背包问题2.1背包装最多问题416.分割等和子集1049.最后一块石头的重量II2.2凑满背包方法数问题494.目标和2.3双重维度问题474.一和零3、完全背包问题3.1凑满组合问题518.零钱兑换II3.2... 查看详情
算法----01背包问题和完全背包问题leetcode系列问题题解(代码片段)
背包问题1、01背包入门1.1二维背包1.2一维背包2、01背包问题2.1背包装最多问题416.分割等和子集1049.最后一块石头的重量II2.2凑满背包方法数问题494.目标和2.3双重维度问题474.一和零3、完全背包问题3.1凑满组合问题518.零钱兑换II3.2... 查看详情
动态规划——完全背包拓展问题(代码片段)
完全背包问题给定你一个固定的背包容量capacity，和两个数组weigth,value，分别表示下标为i的物品的重量和价值，每件物品有无数件，问你背包能够存放下物品的最大价值是多少？这与之前的01背包极其拓展问题... 查看详情
模板背包
（死亡）本文部分参照背包九讲（链接点这里）先看三道题：01背包，完全背包，混合背包请记住这个题面：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。有... 查看详情
完全背包——01背包方法数(代码片段)
这两天搞完01背包之后学习了完全背包这个完全背包是指物品数量无限，让自己来装考虑一下状态转移f[i][j]=max(f[i-1][j])尚未选择第i种物品,f[i][j]=max(f[i][j-w[i]+v[i]]);从第i键物品中选择一个显然状态是由不拿当前物品上一层的最优... 查看详情