0/1背包问题应用案例
2023-09-11 14:21:06 时间
//转换为0/1背包问题,求解在bagsize为某值的时候,有多少种组合方式,dp[j]表示在容量为j的情况下,有多少种组合方式 def findTargetSumWays(self, nums: List[int], target: int) -> int: sumValue = sum(nums) if target > sumValue or (sumValue + target) % 2 == 1: return 0 bagSize = (sumValue + target) // 2 dp = [0] * (bagSize + 1) dp[0] = 1 //外层遍历,用来判断加上nums[i]后,满足内层各种容量j的情况有多少种, //每加遍历一个nums[j],dp[j]就更新一次,相当于随着物品的增加,不断更新来判断 //遍历变nums后,dp[j]各容量的真实情况就全部更新完毕了 for i in range(len(nums)): for j in range(bagSize, nums[i] - 1, -1): dp[j] += dp[j - nums[i]] return dp[bagSize]
相关文章
- python数据分析高阶应用技巧-pandas库聚合案例【 groupby().apply()写法强化】
- Google Earth Engine APP——UI地图加载一个高程显示标签并显示高程案例
- Google Earth Engine(GEE)——MODIS 影像LST地表温度随时间变化的趋势案例分析
- Google Earth Engine(GEE)——MODIS数据蒸散发数据北京市2001—2020年四季平均值案例分析
- 【MATLAB教程案例35】指纹识别系统中图像处理环节相关理论学习和MATLAB仿真实现——图像二值化、锐化、细化、特征提取、伪特征去除等综合应用学习
- 【MATLAB教程案例14】基于ACO蚁群优化算法的函数极值计算matlab仿真及其他应用
- 【FPGA教程案例100】深度学习1——基于CNN卷积神经网络的手写数字识别纯Verilog实现,使用mnist手写数字数据库
- 网络安全产品之堡垒机介绍以及应用案例
- Airtest自动化测试实操案例 | Windows应用篇
- 哈佛教授用3个大数据案例告诉你:大数据,重要的不是数据!
- 线程高级应用-心得7-java5线程并发库中阻塞队列Condition的应用及案例分析
- 线程高级应用-心得3-线程范围内的共享变量以及应用场景及面试题案例分析
- 【定时任务】CronExpression表达式详解和案例(转)
- 《Android 应用案例开发大全(第二版)》——2.8节工具常量类
- 《用于物联网的Arduino项目开发:实用案例解析》—— 2.3 Arduino Uno的无线连接(WiFi)
- MSSQL - 应用案例 - Event Notification + Service Broker构建死锁自动收集系统
- 《Android 应用案例开发大全(第3版)》——第2.3节壁纸的基本框架
- 《Android 应用案例开发大全(第3版)》——第2.8节壁纸中的着色器开发
- Ant Design 3.0 使用案例
- SwiftUI 数字显示格式应用大全实现数字格式化为货币值、百分比值、序数值(Swift NumberFormatter 应用案例)
- 《Mahout算法解析与案例实战》一一1.1 Mahout应用背景
- DBA生存警示:主备环境误操作案例及防范建议
- 【Unity3D应用案例系列】时钟、钟表小组件开发
- 【快应用】for循环数据不渲染指导案例
- 从实际案例,看视频信息化在教育行业的应用现状
- python第十四课--排序及自定义函数之自定义函数(案例四)
- 分享一个基于ligerui的系统应用案例ligerRM V2(权限管理系统)(提供下载)