题目分析
众所周知,dp的题目状态分析确定一般都是要基于大量的经验下得出的,所以dp也是一门关于经验的学科(逃
所以dp的题目最好的一个学习方式就是每次按照既定流程去分析,然后总结状态分析的确定,以后看见了类似的题目就可以直接分析得出f的状态。
ysdp分析法:
1.状态分析,确定状态表示: f[i,j] 的集合和属性
在0-1背包问题中,
f[i,j]表示的集合是:只从前i个物品中选,且体积不超过j的选法集合 (整个解题的根本关键)
f[i,j]的数值属性是:max(min,数量)
2.状态转移
在01背包问题中,每个物品只能选一次,所以我们对于当前状态,可以分为两种情况:1.选 2.不选
将这个集合分为两类,一类是选的集合,一类是不选的集合。
不选的话,f[i j] 很明显就和 f[i-1, j] 的数值是一样的(根据集合的定义)
选的话, f[i j] = f[i-1,j-v[i]]+w[i],也就是说如果选的话,我们的值就来源于在前i-1个物品中,体积不超过j-v[i]的集合中的最大值再加上当前物品的价值。
两者中取一个max即可得出f[i,j] -> 在前i个物品中,体积不超过j的集合中的最大值,也就是题目要我们求的,返回f[n][m]即为所求。
样例
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例
8
朴素写法
N = 1010 #物品容量
V = 1010 #体积容量
v = [0]*N
w = [0]*N
f = [[0]*V for i in range(N)]
def dp():
for i in range(1,n+1):
for j in range(1,m+1):
f[i][j] = f[i-1][j]
if j>=v[i]:
f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i])
return f[n][m]
n,m = map(int,input().split())
for i in range(1,n+1):
a,b = map(int,input().split())
v[i] = a
w[i] = b
print(dp())
优化写法
优化写法其实就是对代码做一个等价变换,至于为什么j要从高到低遍历,是为了防止用到当前层数的数据
N = 1010 #物品容量
V = 1010 #体积容量
v = [0]*N
w = [0]*N
f = [0]*V
def dp():
for i in range(1,n+1):
for j in range(m,v[i]-1,-1):
f[j] = max(f[j],f[j-v[i]]+w[i])
return f[m]
n,m = map(int,input().split())
for i in range(1,n+1):
a,b = map(int,input().split())
v[i] = a
w[i] = b
print(dp())