Written with StackEdit.
特征
每件物品不限数量
思路
转化为0/1背包(?) 每个物体尽可能多放(Why?) 递推式为:
F
(
i
,
j
)
=
M
a
x
{
F
(
i
−
1
,
w
−
k
w
[
i
]
)
+
k
v
[
i
]
}
,
∀
k
w
[
i
]
<
w
F(i,j)=Max\{F(i-1,w-kw[i])+kv[i]\} ,\forall kw[i]<w
F(i,j)=Max{F(i−1,w−kw[i])+kv[i]},∀kw[i]<w 其他思路和01背包相同. 检查每一个K不会造成越界的k. 0/1背包就是完全背包的退化问题.
代码
'''
@Description:
@Date: 2019-10-31 22:20:43
@Author: I-Hsien
@LastEditors: I-Hsien
@LastEditTime: 2019-10-31 22:42:45
'''
def build(set,weight
):
if set==[] or weight
==0:
return 0
kr
=[]
k
=0
while(k
*set[-1][0]<=weight
):
kr
.append
(build
(set[:-1],weight
-k
*set[-1][0])+k
*set[-1][1])
k
+=1
return max(kr
)
if __name__
=="__main__":
temp
=input().split
()
maxweight
=int(temp
[0])
quantity
=int(temp
[1])
array
=[]
for _
in range(quantity
):
tor
=input().split
()
array
.append
((int(tor
[0]),int(tor
[1])))
print(int(build
(array
,maxweight
)))
果然又TLE了… 这递归不是等着爆栈吗…
