0-1背包问题实现及Leetcode 132

2024-08-21 07:48

本文主要是介绍0-1背包问题实现及Leetcode 132,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

0-1背包问题

  • 问题描述

给定一组多个(n)物品,每种物品都有自己的重量( w i w_i wi)和价值( v i v_i vi),在限定的总重量/总容量(C)内,选择其中若干个(也即每种物品可以选0个或1个),设计选择方案使得物品的总价值最高。

  • 思路:
    定义问题dp(i, W)为前i个物品中,选择的重量不超过W。对于第i个物品,要么不选;要没选,因此dp公式为:
    dp(i, W) = max(dp(i-1, W), dp(i-1, W- W i W_i Wi)+ v i v_i vi)

  • 代码如下:

def package_01(n, weights, values, C):dp = [[0]*(C+1) for _ in range(n+1)]for i in range(1, n+1):for j in range(1, C+1):dp[i][j] = dp[i-1][j]if j-weights[i-1] > 0:dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])from pprint import pprintpprint(dp)return dp[n][C]n=5
c=10
w=[2,2,6,5,4]
v=[6,3,5,4,6]
print(package_01(n, w, v, c))
  • 输出结果
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],[0, 0, 0, 6, 6, 6, 6, 6, 6, 6, 6],[0, 0, 0, 6, 6, 9, 9, 9, 9, 9, 9],[0, 0, 0, 6, 6, 9, 9, 9, 9, 11, 11],[0, 0, 0, 6, 6, 9, 9, 9, 10, 11, 13],[0, 0, 0, 6, 6, 9, 9, 12, 12, 15, 15]]
15

leetcode 132

  • 问题描述
Given a string s, partition s such that every substring of the partition is a palindrome.Return the minimum cuts needed for a palindrome partitioning of s.Example:Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.
  • 思路见注释,代码如下:
class Solution:def minCut(self, s):""":type s: str:rtype: int"""n = len(s)dp = [i-1 for i in range(n+1)]for mid in range(0, n):for offset in range(0, n): # 奇数长度回文if mid-offset >= 0 and mid+offset < n and s[mid-offset] == s[mid+offset]:dp[mid+offset+1] = 0 if mid-offset == 0 else min(dp[mid+offset+1], 1+dp[mid-offset])else:breakfor offset in range(0, n): # 偶数长度回文if mid-offset >= 0 and mid+offset+1 < n and s[mid-offset] == s[mid+offset+1]:dp[mid+offset+2] = 0 if mid-offset == 0 else min(dp[mid+offset+2], 1+dp[mid-offset])else:break
#         print(dp)return dp[-1]

这篇关于0-1背包问题实现及Leetcode 132的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1092553

相关文章

java如何实现高并发场景下三级缓存的数据一致性

《java如何实现高并发场景下三级缓存的数据一致性》这篇文章主要为大家详细介绍了java如何实现高并发场景下三级缓存的数据一致性,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 下面代码是一个使用Java和Redisson实现的三级缓存服务,主要功能包括:1.缓存结构:本地缓存:使

SpringBoot 异常处理/自定义格式校验的问题实例详解

《SpringBoot异常处理/自定义格式校验的问题实例详解》文章探讨SpringBoot中自定义注解校验问题,区分参数级与类级约束触发的异常类型,建议通过@RestControllerAdvice... 目录1. 问题简要描述2. 异常触发1) 参数级别约束2) 类级别约束3. 异常处理1) 字段级别约束

如何在Java Spring实现异步执行(详细篇)

《如何在JavaSpring实现异步执行(详细篇)》Spring框架通过@Async、Executor等实现异步执行,提升系统性能与响应速度,支持自定义线程池管理并发,本文给大家介绍如何在Sprin... 目录前言1. 使用 @Async 实现异步执行1.1 启用异步执行支持1.2 创建异步方法1.3 调用

Spring Boot配置和使用两个数据源的实现步骤

《SpringBoot配置和使用两个数据源的实现步骤》本文详解SpringBoot配置双数据源方法,包含配置文件设置、Bean创建、事务管理器配置及@Qualifier注解使用,强调主数据源标记、代... 目录Spring Boot配置和使用两个数据源技术背景实现步骤1. 配置数据源信息2. 创建数据源Be

在MySQL中实现冷热数据分离的方法及使用场景底层原理解析

《在MySQL中实现冷热数据分离的方法及使用场景底层原理解析》MySQL冷热数据分离通过分表/分区策略、数据归档和索引优化,将频繁访问的热数据与冷数据分开存储,提升查询效率并降低存储成本,适用于高并发... 目录实现冷热数据分离1. 分表策略2. 使用分区表3. 数据归档与迁移在mysql中实现冷热数据分

linux批量替换文件内容的实现方式

《linux批量替换文件内容的实现方式》本文总结了Linux中批量替换文件内容的几种方法,包括使用sed替换文件夹内所有文件、单个文件内容及逐行字符串,强调使用反引号和绝对路径,并分享个人经验供参考... 目录一、linux批量替换文件内容 二、替换文件内所有匹配的字符串 三、替换每一行中全部str1为st

SpringBoot集成MyBatis实现SQL拦截器的实战指南

《SpringBoot集成MyBatis实现SQL拦截器的实战指南》这篇文章主要为大家详细介绍了SpringBoot集成MyBatis实现SQL拦截器的相关知识,文中的示例代码讲解详细,有需要的小伙伴... 目录一、为什么需要SQL拦截器?二、MyBATis拦截器基础2.1 核心接口:Interceptor

Python错误AttributeError: 'NoneType' object has no attribute问题的彻底解决方法

《Python错误AttributeError:NoneTypeobjecthasnoattribute问题的彻底解决方法》在Python项目开发和调试过程中,经常会碰到这样一个异常信息... 目录问题背景与概述错误解读:AttributeError: 'NoneType' object has no at

SpringBoot集成EasyPoi实现Excel模板导出成PDF文件

《SpringBoot集成EasyPoi实现Excel模板导出成PDF文件》在日常工作中,我们经常需要将数据导出成Excel表格或PDF文件,本文将介绍如何在SpringBoot项目中集成EasyPo... 目录前言摘要简介源代码解析应用场景案例优缺点分析类代码方法介绍测试用例小结前言在日常工作中,我们经

基于Python实现简易视频剪辑工具

《基于Python实现简易视频剪辑工具》这篇文章主要为大家详细介绍了如何用Python打造一个功能完备的简易视频剪辑工具,包括视频文件导入与格式转换,基础剪辑操作,音频处理等功能,感兴趣的小伙伴可以了... 目录一、技术选型与环境搭建二、核心功能模块实现1. 视频基础操作2. 音频处理3. 特效与转场三、高