当前位置: 首页 > news >正文

微商网站建设市场营销的八个理论

微商网站建设,市场营销的八个理论,常用的英文网站字体,软件设计包括哪些内容0-1背包问题理论基础 分割等和子集1. 0-1背包问题理论基础(二维数组实现)2. 0-1背包问题理论基础 二(一维数组实现)1. 0-1背包问题理论基础(二维数组实现) 背包问题一般分为这几种: 0-1背包问题:有n件物品和一个最多能背重量为w…

0-1背包问题理论基础 分割等和子集

  • 1. 0-1背包问题理论基础(二维数组实现)
  • 2. 0-1背包问题理论基础 二(一维数组实现)

1. 0-1背包问题理论基础(二维数组实现)

背包问题一般分为这几种:
在这里插入图片描述
0-1背包问题:有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。

二维dp数组01背包

  • 确定dp数组以及下标的含义
    对于背包问题,有一种写法, 是使用二维数组,即dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少。
  • 确定递推公式
    再回顾一下dp[i][j]的含义:从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少。
    那么可以有两个方向推出来dp[i][j],
    • 不放物品i:由dp[i - 1][j]推出,即背包容量为j,里面不放物品i的最大价值,此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时,物品i无法放进背包中,所以被背包内的价值依然和前面相同。)
    • 放物品i:由dp[i - 1][j - weight[i]]推出,dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值,那么dp[i - 1][j - weight[i]] + value[i] (物品i的价值),就是背包放物品i得到的最大价值
      所以递归公式: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
  • dp数组如何初始化
  • 确定遍历顺序 先遍历物品更好理解。
  • 举例推导dp数组
def test_2_wei_bag_problem1(bag_size, weight, value) -> int: rows, cols = len(weight), bag_size + 1dp = [[0 for _ in range(cols)] for _ in range(rows)]# 初始化dp数组. for i in range(rows): dp[i][0] = 0first_item_weight, first_item_value = weight[0], value[0]for j in range(1, cols): 	if first_item_weight <= j: dp[0][j] = first_item_value# 更新dp数组: 先遍历物品, 再遍历背包. for i in range(1, len(weight)): cur_weight, cur_val = weight[i], value[i]for j in range(1, cols): if cur_weight > j: # 说明背包装不下当前物品. dp[i][j] = dp[i - 1][j] # 所以不装当前物品. else: # 定义dp数组: dp[i][j] 前i个物品里,放进容量为j的背包,价值总和最大是多少。dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cur_weight]+ cur_val)print(dp)if __name__ == "__main__": bag_size = 4weight = [1, 3, 4]value = [15, 20, 30]test_2_wei_bag_problem1(bag_size, weight, value)

2. 0-1背包问题理论基础 二(一维数组实现)

def test_1_wei_bag_problem():weight = [1, 3, 4]value = [15, 20, 30]bag_weight = 4# 初始化: 全为0dp = [0] * (bag_weight + 1)# 先遍历物品, 再遍历背包容量for i in range(len(weight)):for j in range(bag_weight, weight[i] - 1, -1):# 递归公式dp[j] = max(dp[j], dp[j - weight[i]] + value[i])print(dp)test_1_wei_bag_problem()

416. 分割等和子集

给你一个 只包含正整数 的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

只有确定了如下四点,才能把01背包问题套到本题上来。

  • 背包的体积为sum / 2
  • 背包要放入的商品(集合里的元素)重量为 元素的数值,价值也为元素的数值
  • 背包如果正好装满,说明找到了总和为 sum / 2 的子集。
  • 背包中每一个元素是不可重复放入。
    以上分析完,我们就可以套用01背包,来解决这个问题了。
class Solution:def canPartition(self, nums: List[int]) -> bool:target = sum(nums)if target % 2 == 1: return Falsetarget //= 2dp = [0] * 10001for i in range(len(nums)):for j in range(target, nums[i] - 1, -1):dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])return target == dp[target]
http://www.mmbaike.com/news/52091.html

相关文章:

  • 怎么做高端网站seo点击软件手机
  • 做网站难吗 挣钱吗百度电商平台app
  • 电子商务建立网站前期准备企业官网定制设计
  • 常州网站建设策划互联网营销推广公司
  • 深圳做网站的公司枫树seo
  • 寺庙网站开发免费的网络推广渠道
  • 西安商城网站开发免费外链网站seo发布
  • 国外做的比较好的展台网站百度游戏客服在线咨询
  • 政府建设网站做网站的流程与步骤
  • 网站广告策划株洲疫情最新情况
  • 网站建设推广专家百度快照和广告的区别
  • 云南网站建设公司1元购买域名
  • 新闻网站抓取做舆情监测输入关键词进行搜索
  • 海北营销网站建设公司电商关键词工具
  • 中国优秀网站seo技术培训广东
  • 网站ps多大尺寸佛山快速排名seo
  • 遵化市城乡建设规划局网站网络管理系统
  • 网站建设的企业目标外链吧官网
  • 百度免费建个人网站百度竞价代运营公司
  • 一个空间怎么做多个网站网上的推广
  • 越秀企业网站建设国际新闻消息
  • 深圳网站建设深icp备百度百度
  • 网站开发2008互联网培训
  • 门户网站首页seo入门培训课程
  • 做外贸网站有哪些西藏自治区seo 标题 关键词优化
  • 网页设计图片路径怎么写seo网站外包公司
  • 太原顶呱呱做网站地址电话seo咨询岳阳
  • 手机网络代理怎么关闭seo排名怎样
  • wordpress最漂亮的主题宁波谷歌seo推广
  • 西安做网站的在哪把百度网址大全设为首页