小明的背包
1.小明的背包1 （01背包）
题目描述
小明有一个容量为 V 的背包。
这天他去商场购物，商场一共有 N件物品，第 i件物品的体积为 wi，价值为 vi。
小明想知道在购买的物品总体积不超过 V 的情况下所能获得的最大价值为多少，请你帮他算算。
输入描述
输入第 1 行包含两个正整数 N,V表示商场物品的数量和小明的背包容量。
第 2∼N+1 行包含 2个正整数 w,v表示物品的体积和价值。
1≤N≤10^2， 1≤V≤10^3，1≤wi,vi≤10^3。
输出描述
输出一行整数表示小明所能获得的最大价值。
输入输出样例
示例 1
输入
5 201 62 53 85 153 3输出
37
二维
定义：dp[i][j]: 前 i个物品，背包容量 j下的最优解
状态转移方程：
-
当前背包容量不够 j < v[i]，所以没法选第 i个物品，答案只能从前 i-1个物品最优解转移而来：dp[i][j] = dp[i-1][j]；
-
当前背包容量够，就要决策选与不选第 i个物品 ：
选：dp[i][j] = dp[i-1][j-v[i]] + w[i]
不选：dp[i][j] = dp[i-1][j]
所以答案从这俩个选择中取最大值也就是 dp[i][j] = max(dp[i - 1][j], dp[i-1][j-v[i]] + w[i])
maxn=1005w=[0 for i in range(maxn)]v=[0 for i in range(maxn)]dp=[[0 for i in range(maxn)]for j in range(maxn)]n,m=map(int,input().split())for i in range(1,n+1): a,b=map(int,input().split()) w[i]=a v[i]=bfor i in range(n+1): for j in range(m+1): if j<v[i]: dp[i][j]=dp[i-1][j] else: dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])print(dp[n][m])一维
将状态 dp[i][j] 优化到一维 dp[j]，为什么可以这样变形呢？
我们发现转移方程式完全和 i变量没有关系嘛，那是不是意味着可以把它优化掉呢。
定义：dp[j] 为 n件物品，背包容量 j下的最优解。
状态转移方程： dp[j] = max(dp[j], dp[j - v[i]] + w[i])
在二维情况下，状态 dp[i][j] 是由上一轮 i - 1 的状态得来的，dp[i][j]与 dp[i - 1][j]是独立的。一维情况下，状态 dp[j] 是在自身的基础上滚动覆盖，因此我们在枚举 j 的时候应该从大到小枚举，这又是为什么呢？
假设当前枚举 i = 3的情况， 那么此时 dp[j]中保存的是上一轮枚举 i = 2的情况，当我们枚举 j 时由于 j - v[i] 肯定比 j小，而比 j 小的 i = 2的 dp[j]的状态已经被 i = 3的覆盖了，也叫做污染了，所以我们就没办法从 i = 2的状态转移过来，而从大到小就不会产生这个问题。
例子：
物 w v
0 1 15
1 3 20
2 4 30
正序遍历：
dp[1]=dp[1-1]+15=15
dp[2]=dp[2-1]+15=30
倒序遍历
dp[2]=dp[2-1]+15=15
dp[1]=dp[1-1]+15=15
maxn=1050w=[0 for i in range(maxn)]v=[0 for i in range(maxn)]dp=[0 for i in range(maxn)]n,m=map(int,input().split())for i in range(1,n+1): a,b=map(int,input().split()) w[i]=a v[i]=bfor i in range(1,n+1): for j in range(m,w[i]-1,-1): dp[j]=max(dp[j],dp[j-w[i]]+v[i])print(dp[m])2.小明的背包2(完全背包）
题目介绍
小明有一个容量为 V 的背包。
这天他去商场购物，商场一共有 N种物品，第 i 种物品的体积为 wi，价值为vi，每种物品都有无限多个。
小明想知道在购买的物品总体积不超过V 的情况下所能获得的最大价值为多少，请你帮他算算。
输入描述
输入第 1行包含两个正整数 N,V，表示商场物品的数量和小明的背包容量。
第 2∼N+1 行包含 2个正整数 w,v，表示物品的体积和价值。
1≤N≤10^3，1≤V≤10^3，1≤wi,vi≤10^3。
输出描述
输出一行整数表示小明所能获得的最大价值。
输入输出样例
示例 1
输入
5 201 62 53 85 153 3输出
120
那么这个核心式子和之前讲的01背包问题十分类似。 于是我们想到进一步的空间优化，不过由于完全背包和01背包不同的地方第二重循环需要正序枚举，因为要先处理小容量，后大容量。
二维 ：
maxn=1005w=[0 for i in range(maxn)]v=[0 for i in range(maxn)]dp=[[0 for i in range(maxn)]for j in range(maxn)]n,m=map(int,input().split())for i in range(1,n+1): a,b=map(int,input().split()) w[i]=a v[i]=bfor i in range(n+1): for j in range(m+1): if j<v[i]: dp[i][j]=dp[i-1][j] else: dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i])print(dp[n][m])一维：
maxn=1050w=[0 for i in range(maxn)]v=[0 for i in range(maxn)]dp=[0 for i in range(maxn)]n,m=map(int,input().split())for i in range(1,n+1): a,b=map(int,input().split()) w[i]=a v[i]=bfor i in range(1,n+1): for j in range(w[i],m+1): dp[j]=max(dp[j],dp[j-w[i]]+v[i])print(dp[m])3.小明的背包3（多重背包）
我们知道 01 背包是对每种物品取和不取的状态进行 dp 转移。
我们可以考虑一个简单的版本， 如果我们si 全部拆分成一件一件的物品，那么是不是就可以转化成 01 背包来做了，但是这样物品最多就有N∗si 件，并不满足 01 背包的复杂度。
现在考虑优化，下面介绍一种二进制优化：
- 首先我们知道一个实数都能被二进制表示
- 假如实际 10 件物品中取 7件最优，那么在实际的遍历过程我们一件一件询问是取了最好还是不取最好
- 现在将 10件物品分堆，我们将 10 件物品分成 4堆：2^0 = 1, 2^1=2,2^2= 4以及10-（1 + 2 + 4） = 3，那么我们每一堆每一堆的询问是否能和一件一件询问一样呢?不难看出上面 4 堆每堆取与不取包括了1−10的所有状态
- 那我们按照二进制优化去分堆之后，再转化成 01 背包，这样复杂度就能接受了。
- 例子：如果第i种物品有13个，根据这种思路，13拆分成1,2,4,6。只需要将这种物品拆分成4个物品，这四个物品的体积和价值分别是（Wi,Vi），（2Wi,2Vi），（4Wi,4Vi），（6Wi,6Vi），而不是13个物品，这就降低了时间复杂度和空间复杂度。
maxn=20010dp=[0 for i in range(maxn)]w=[0 for i in range(maxn<<1)]v=[0 for i in range(maxn<=(1<<b): x=int(1<0: cnt+=1 w[cnt]=s*ww v[cnt]=s*vvfor i in range(1,cnt+1): for j in range(n,w[i]-1,-1): dp[j]=max(dp[j],dp[j-w[i]]+v[i])print(dp[n])4.小明的背包4（混合背包）
题目描述
小明有一个容量为 V 的背包。
这天他去商场购物，商场一共有 N种物品，第 i种物品的体积为 wi，价值为 vi，数量为 si。
小明想知道在购买的物品总体积不超过 VV 的情况下所能获得的最大价值为多少，请你帮他算算。
输入描述
输入第 1行包含两个正整数 N,V，表示商场物品的数量和小明的背包容量。
第 2∼N+1 行包含 3个正整数 w,v,s表示物品的体积和价值。
1≤N≤10^3，1≤V≤2×10^3，1≤wi,vi≤2×10^3，0≤si≤2×10^3。
如果 si=0 表示该商品有无限个。
输出描述
输出一行整数表示小明所能获得的最大价值。
因此我们将 01背包归入多重背包， 对每种物品的数量进行讨论，如果是完全背包就按照完全背包的转移方法进行转移，是多重2背包就用多重背包的方法进行状态转移，这样我们就完成了混合背包的求解。
maxn=20010dp=[0 for i in range(maxn)]w=[0 for i in range(maxn<<1)]v=[0 for i in range(maxn<<1)]k=[0 for i in range(maxn<=(1<<b): x=int(1<0: cnt+=1 w[cnt]=s*ww v[cnt]=s*vv k[cnt]=1for i in range(1,cnt+1): if k[i]==0: for j in range(w[i],n+1): dp[j]=max(dp[j],dp[j-w[i]]+v[i]) else: for j in range(n,w[i]-1,-1): dp[j]=max(dp[j],dp[j-w[i]]+v[i])print(dp[n])5.小明的背包5
题目描述
小明有一个容量为 V 的背包。
这天他去商场购物，商场一共有 N组物品，第 i组里有 si 件物品，物品的体积为 w，价值为 v，对于每一组只能购买一件物品。
小明想知道在购买的物品总体积不超过 V 的情况下所能获得的最大价值为多少，请你帮他算算。
输入描述
输入第 11 行包含两个正整数 N,V，表示商场物品的数量和小明的背包容量。
接下来有 N组数据，对于每组数据的输入如下：
- 第一行输入一个整数 s，表示该组的物品个数。
- 接下来 ss 行每行包含两个整数 w,v，表示物品的体积和价值。
1≤N,V≤10^2，1≤s≤10^2，1≤w,v≤10^3。
输出描述
输出一行整数表示小明所能获得的最大价值
maxn=1050dp=[0 for i in range(maxn)]v=[[0 for i in range(maxn)]for j in range(maxn)]s=[0 for i in range(maxn)]w=[[0 for i in range(maxn)]for j in range(maxn)]n,m=map(int,input().split())for i in range(1,n+1): s[i]=int(input()) for j in range(1,s[i]+1): w[i][j],v[i][j]=map(int,input().split())for i in range(1,n+1): for j in range(m,-1,-1): for k in range(1,s[i]+1): if j>=w[i][k]: dp[j]=max(dp[j],dp[j - w[i][k]]+v[i][k])print(dp[m])
