专栏首页Petrichor的专栏【leetcode】背包问题

【leetcode】背包问题

思路

一般用动态规划(DP)。

输入参数

  • W:各个物品的重量;
  • V:各个物品的价值;
  • carry:最大承重为carry的背包;
  • N:物品件数。

0-1背包

每件物品只能选一次。

def bag_01(V, W, carry, N):
    res = [0] * (carry+1)
    for i in range(N):
        for j in range(carry, W[i]-1, -1):
            res[j] = max(res[j], res[j-W[i]]+V[i])
    return res[-1]

完全背包

每件物品可以选无数次。

完全背包的特点恰是每种物品可选无限件,所以就可以并且必须采用 w = W[i]…carry 的顺序循环:

def bag_absolute(V, W, carry, N):
    res = [0] * (carry+1)
    for i in range(N):
        for j in range(W[i], carry+1):	# 这是和01背包唯一的区别:正序遍历
            res[j] = max(res[j], res[j-W[i]]+V[i])
    return res[-1]

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode: 40. Combination Sum II

    JNingWei
  • leetcode: 29. Divide Two Integers [✗]

    JNingWei
  • leetcode: 96. Unique Binary Search Trees

    JNingWei
  • 小程序体验版 新用户登录不了

    console.log(wx.getStorageSync("userInfo").id )

    用户6663311
  • [PHP] 算法-两个n位的二进制整数相加问题PHP实现

    两个n位二进制数分别存储在两个n元数组A和B中,这两个整数的和存在一个n+1元的数组C中 答: 此问题主要是考察相加进位的问题,元素1+1 =0 并且往前进一位...

    陶士涵
  • 借助Web云开发数据库,让你的静态H5“动”起来!

    如果你设计出了一个好看好玩的 H5 ,却碍于没有好用的后端来存储用户的数据,那不妨试试云开发 https://cloud.tencent.com/product...

    腾讯云开发TCB
  • 前端基础-分组/捕获和反向引用

    子表达式 在正则表达式中,通过一对圆括号括起来的内容,我们就称之为“子表达式”。如: var reg = /\d(\d)\d/gi;

    cwl_java
  • Express.js 4,Node.js,MongoDB REST API 简易教程

    教程内容 采用测试驱动开发的方式,开发一个简单的 REST API,包括基本的 POST/GET/PUT/DELETE 操作 先编写好针对各个接口的测试代码,包...

    dys
  • 【python-leetcode107-树的宽度遍历】二叉树的层次遍历Ⅱ

    给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

    绝命生
  • fastjson:对于Exception中复杂类型(enum,...以及自定义类型)成员的处理

    如果一个Exception类中有枚举类型或其他复杂类型(比如java.util.Date,或自定义类型)的成员,fastjson反序列化会抛出异常。 /...

    用户1148648

扫码关注云+社区

领取腾讯云代金券