通化网站开发,做网站需要备案么,北京 集团公司网站建设,黄骅市人事考试网474. 一和零
题目链接#xff1a;https://leetcode.cn/problems/ones-and-zeroes/submissions/501607337/
思路
之前的背包问题中#xff0c;我们对背包的限制是容量#xff0c;即每个背包装的物品的重量和不超过给定容量#xff0c;这道题的限制是0和1的个数#xff0…474. 一和零
题目链接https://leetcode.cn/problems/ones-and-zeroes/submissions/501607337/
思路
之前的背包问题中我们对背包的限制是容量即每个背包装的物品的重量和不超过给定容量这道题的限制是0和1的个数因此这个背包是二维m和n最多可以装m个0和n个1。数组中的每个元素都是一个物体包含若干个0和1。
1. dp数组定义
dp[i][j]: 最多装i个0和j个1的背包最多能装dp[i][j]个物体。
2. 递推公式
遍历每个物体这个物体有x个0和y个1我们选择装或者不装这个物体。如果不装它那么背包中的物体保持原样如果装它就要为它腾出相应的0和1的位置腾出后背包能最多装dp[i-x][j-y]个物体再加上当前物体即dp[i-x][j-y]1因此递推公式为
dp[i][j] max(dp[i][j], dp[i-x][j-y]1)
3. 初始条件
01背包的dp数组初始化为0就可以。
4. 遍历顺序
外层遍历物体内层分别遍历背包容量的两个维度且倒序遍历。在下面的文章中讲过具体细节代码随想录算法训练营第四十六天动态规划篇|01背包滚动数组方法-CSDN博客
5. 举例推导dp数组
以输入[10,0001,111001,1,0]m 3n 3为例
最后dp数组的状态如下所示 代码实现
class Solution(object):def findMaxForm(self, strs, m, n): # m个0n个1dp [[0]*(n1) for _ in range(m1)]# zeros, ones 0, 0for s in strs:zeros s.count(0)ones s.count(1)for i in range(m, zeros-1, -1):for j in range(n, ones-1, -1):dp[i][j] max(dp[i][j], dp[i-zeros][j-ones]1)return dp[m][n] 完全背包理论基础
题目链接题目页面
思路
完全背包允许物体被重复放入它的代码与01背包的区别在于遍历顺序。01背包对内部容量的循环是从大到小遍历为了保证每个物品仅被添加一次。而完全背包的物品是可以添加多次的所以要从小到大去遍历。
代码实现
N, V map(int, input().split())
weight, value [0]*N,[0]*N
for i in range(N):weight[i], value[i] map(int,input().split())dp [0]*(V1)
for i in range(N):for j in range(weight[i], V1):dp[j] max(dp[j], dp[j-weight[i]] value[i])
print(dp[j])
