背包问题

算法动态规划

发布时间 : 2024-06-01 15:22

字数:158 阅读 :

背包问题技巧

1、如果是0-1背包，数组中的元素不可重复使用，nums放外循环，target放内循环且倒序：

for num in nums:
	for j in range(target, num-1, -1):

2、如果是完全背包，数组中的元素可重复使用，nums放外循环，target放内循环且正序：

for num in nums:
	for j in range(num, target+1):

3、如果组合问题需考虑元素之间的顺序，需将target放在外循环，将nums放在内循环。

for i in range(1, target+1):
    for num in nums:

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1216271933@qq.com