首页 > 编程语言 >代码随性训练营第四十六天(Python)| 139.单词拆分 、多重背包

代码随性训练营第四十六天(Python)| 139.单词拆分 、多重背包

时间:2023-11-30 17:55:57浏览次数:51  
标签:背包 weight bag 随性 Python range 遍历 第四十六 dp

139.单词拆分

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False] * (len(s) + 1)
        dp[0] = True

        # 求排列先遍历背包再遍历物品
        for i in range(len(s) + 1):
            for j in range(i):
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True # dp[j] 可以被拆分单词,并且 s[j:i] 在字典中。s[0:i] 也可以被拆分单词
                    break
        return dp[len(s)]

[多重背包]
有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用,每件耗费的空间是Ci ,价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量,且价值总和最大。

def multi_bag(weight, value, count, bag_weight):
    dp = [0] * (bag_weight + 1)

    for i in range(len(weight)): # 先遍历物品
        for j in range(bag_weight, weight[i] - 1, -1): # 再遍历背包
            # 遍历个数
            for k in range(1, count[i] + 1):
                if j - k * weight[i] >= 0:
                    dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i])

        # 打印 dp
        print(" ".join([str(dp[j]) for j in range(bag_weight + 1)]))

    return dp[bag_weight]


if __name__ == "__main__":
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bag_weight = 4
    count = [2, 3, 2]
    res = multi_bag(weight, value, count, bag_weight)
    print(res)

标签:背包,weight,bag,随性,Python,range,遍历,第四十六,dp
From: https://www.cnblogs.com/yixff/p/17867933.html

相关文章

  • 软件测试/人工智能|教你轻松掌握Python输入与输出
    简介Python是一种流行的编程语言,它具有简洁而强大的输入输出功能,允许开发者与用户交互并显示结果。本文将介绍Python中的输入和输出方法。输入(Input)Python中获取用户输入的常用方法是使用input()函数。这个函数允许程序暂停执行,等待用户输入内容,并将输入的内容作为字符串返回......
  • 面向对象---入门级(最基础的部分)python
    #面向对象---入门#思想或者宗旨:抽象、封装、继承、多态#完成对一个类的创建,(先抽象)(类名一般大写)classStudent:name=""age=""sex=""score=""#访问类里的元素name="李四"Student.name="张三"print(Student.name)print(name)#name=“......
  • python打包本地pip包需要注意哪些问题
    参考资料:https://packaging.python.org/tutorials/packaging-projects/提到Python的包管理器,大多数人都会想到pip和conda,其中又尤以pip简单好用。那么如果有一天你写了一个有用的项目,想要发布给公众,或者实现方便的安装,那么你可能就会想要自己去打包一个pip包。毕竟,......
  • Python——第四章:函数的递归调用
    递归: 函数自己调用自己递归如果没有任何东西拦截的话.它默认就是一个死循环deffunc()func()func()因此递归调用的时候需要有判断,来退出循环deffunc()ifxxxxx:returnfunc()func()这里就用到了return来充当循环中的break作用。如......
  • 代码随想训练营第四十五天(Python)| 70. 爬楼梯 (进阶)、322. 零钱兑换 、 279.完全平方数
    70.爬楼梯(进阶)1、使用01背包解法classSolution:defclimbStairs(self,n:int)->int:#dp数组代表爬上第i阶有dp[j]种方法dp=[0]*(n+1)dp[0]=1m=2#排列先背包后物品foriinrange(n+1):......
  • Python---GUI----Tkinter
    PythonGUI编程(Tkinter)Python提供了多个图形开发界面的库,几个常用PythonGUI库如下:Tkinter: Tkinter模块(Tk接口)是Python的标准TkGUI工具包的接口.Tk和Tkinter可以在大多数的Unix平台下使用,同样可以应用在Windows和Macintosh系统里。Tk8.0的后续版本......
  • python的websockets库
    安装pipinstallwebsockets分为客户端和服务端两部分  服务端一般与异步的库一起用因为客户端不可能只服务一个客户所以要用异步处理多个客户 以asyncio示例 fromwebsockets.serverimportserveimportwebsocketsimportasyncioasyncdefstart(ws,path):#......
  • Rust std fs 比 Python 慢!真的吗!?
    作者:XuanwoDatabendLabs成员,数据库研发工程师https://github.com/xuanwo我即将分享一个冗长的故事,从OpenDAL的op.read()开始,以一个意想不到的转折结束。这个过程对我来说非常有启发性,我希望你也能感受到。我会尽力重现这个经历,并附上我一路学到的教训。让我们开始吧!所......
  • python开发之个微群聊机器人开发
    请求URL:http://域名地址/inviteChatRomMember请求方式:POST请求头Headers:Content-Type:application/jsonAuthorization:login接口返回参数:参数名必选类型说明wId是string登录实例标识chatRomI是String群userList是String群成员微信id,多个已","分割返回数据:参数名类型说明codestring1......
  • python提取图片中文字
    一.安装tesseract-ocr1.1tesseract-ocr下载下载地址:Indexof/tesseract(uni-mannheim.de)1.2完成tesseract-ocr安装,记住安装路径用于配置环境变量1.3配置环境变量将tesseract-ocr的安装路径添加到环境变量的系统变量(PATH)增加一个TESSDATA_PREFIX变量名,变量值还是安装路......