[每日一题] 01背包问题

这篇具有很好参考价值的文章主要介绍了[每日一题] 01背包问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

给定 n 种物品和一背包。物品 i 的重量是 w i w_i wi,其价值为 v i v_i vi ,背包的容量为 C。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大? 对于一种物品,要么装入背包,要么不装。

解法一:暴力递归

可能性分析:

f ( i, rest ) 物品 i ,背包容量为 rest 时,能装入的物品的最大总价值。

  • 物品 i 放入背包:res1 = f( i + 1, rest - w[i] )
  • 物品 i 不放入背包:res2 = f( i + 1, rest )
  • 决策:res = max( res1, res2 )

算法模型:从左向右依次对每个元素进行尝试(保留或者丢弃),根据最大值决策。

01背包问题,可能性尝试题里已经明确说明了(放入背包或者丢弃),也有很多其他题,需要自己从题的隐含条件中找到尝试的可能性。

这里的可能性只有两种,也有一些题需要遍历所有可能后(一次递归调用),再决策。

def knapsack01_v1(v, w, C):
    return process1(v, w, 0, C)

def process1(v, w, index, rest):
    if rest < 0: return -1
    if index == len(w): return 0
    p1 = process1(v, w, index + 1, rest)
    p2 = 0
    n = process1(v, w, index + 1, rest - w[index])
    if n != -1:
        p2 = v[index] + n
    return max(p1, p2)

# 代码优化
def knapsack01_v2(v, w, C):
    return process2(v, w, 0, C)

def process2(v, w, index, rest):
    if index == len(w): return 0
    return max(process2(v, w, index + 1, rest),
               process2(v, w, index + 1, rest - w[index]) + v[index] if rest >= w[index] else 0)

解法二:动态规划

row 是 index

col 是 rest

可以从下向上填满矩阵也可以从上向下填满矩阵
[每日一题] 01背包问题

def knapsack01_v2(v, w, C):
    n = len(w)
    dp = [[0] * (C + 1) for _ in range(n + 1)]

    for row in range(n - 1, -1, -1):
        for col in range(1, C + 1):
            dp[row][col] = max(dp[row + 1][col], dp[row + 1][col - w[row]] + v[row] if col >= w[row] else 0)

    return dp[0][C]

解法三:动态规划:滚动数组

根据上图,当前数据 f(i,rest) 只依赖下边临近的一行的数据,所以不需要一个完整的矩阵,需要保存一行数据,进行滚动更新。

注意:滚动更新的方向,只能从右向左。因为 i 行依赖 i + 1 行左边的数据,如果从左向右滚动更新 dp 数组,i 的 rest 之前的数据已经是新数据,没有办法用于后续的滚动更新了

def knapsack01_v4(v, w, C):
    n = len(w)
    dp = [0] * (C + 1)

    for row in range(n - 1, -1, -1):
        for col in range(C, -1, -1):
            dp[col] = max(dp[col], dp[col - w[row]] + v[row] if col >= w[row] else 0)
    return dp[C]
  
  
def knapsack01_v5(v, w, C):
    n = len(w)
    dp = [0] * (C + 1)

    for row in range(n):
        for col in range(C, -1, -1):
            dp[col] = max(dp[col], dp[col - w[row]] + v[row] if col >= w[row] else 0)
    return dp[C]

对数器文章来源地址https://www.toymoban.com/news/detail-515644.html

import random

def generator_random_array(max_value, size):
    return [int(random.random() * max_value) + 1 for _ in range(size)]


def check():
    max_value = 10
    max_size = 10
    for i in range(500):
        size = int(random.random() * max_size)
        w = generator_random_array(max_value, size)
        c = int(random.random() * sum(w))

        v = generator_random_array(max_value, size)
        res1 = knapsack01_v1(w, v, c)
        res2 = knapsack01_v2(w, v, c)
        res3 = knapsack01_v3(w, v, c)
        res4 = knapsack01_v4(w, v, c)
        if res1 != res2 or res1 != res3 or res1 != res4:
            print("ERROR", res1, res2, res3, res4, w, v, c)
    print("OVER!")


check()

到了这里,关于[每日一题] 01背包问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【每日一题Day312】LC2240买钢笔和铅笔的方案数 | 完全背包 数学

    买钢笔和铅笔的方案数【LC2240】 给你一个整数 total ,表示你拥有的总钱数。同时给你两个整数 cost1 和 cost2 ,分别表示一支钢笔和一支铅笔的价格。你可以花费你部分或者全部的钱,去买任意数目的两种笔。 请你返回购买钢笔和铅笔的 不同方案数目 。 一眼背包问题 原来数

    2024年02月10日
    浏览(40)
  • 2023-09-01力扣每日一题

    链接: 2240. 买钢笔和铅笔的方案数 题意: 一共total元,两种笔分别cost1和cost2元,求能买的的笔的所有情况,不要求花光钱 解: 枚举其中一个数字就行 实际代码: 限制: 1 = total, cost1, cost2 = 106

    2024年02月10日
    浏览(34)
  • 【力扣每日一题01】两数之和

    开了一个新专栏,用来记录自己每天刷题,并且也是为了养成每日学习这个习惯,期待坚持一年后的自己! 给定一个整数数组  nums  和一个整数目标值  target ,请你在该数组中找出  和为目标值  target   的那  两个  整数,并返回它们的数组下标。 你可以假设每种输入只

    2024年02月10日
    浏览(49)
  • 2023-08-01 LeetCode每日一题(英雄的力量)

    点击跳转到题目位置 给你一个下标从 0 开始的整数数组 nums ,它表示英雄的能力值。如果我们选出一部分英雄,这组英雄的 力量 定义为: i 0 ,i 1 ,… i k 表示这组英雄在数组中的下标。那么这组英雄的力量为 max(nums[i0],nums[i1] … nums[ik])2 * min(nums[i0],nums[i1] … nums[ik]) 。 请你

    2024年02月14日
    浏览(60)
  • 2023/07/01_leetcode每日一题_1. 两数之和

    给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 一开始审错题了,还以

    2024年02月12日
    浏览(52)
  • 背包问题——01背包|完全背包

    目录 前言背包问题的历史  01背包  1、题目 2、暴力解01背包  Ⅰ、代码 3、动态规划解01背包 Ⅰ、二维dp数组解01背包 1)dp数组的含义  2)递推公式  3)dp数组的初始化  4)遍历顺序的讨论  5、代码  Ⅱ、一维数组解01背包  1)一维数组|滚动数组  2)一维数组的含义及递

    2024年02月02日
    浏览(48)
  • 背包问题(贪心)& 二维01背包问题 Java

    题目描述 有n件物品和一个最大承重为w 的背包。第i件物品的重量是weight[i],每件只能用一次,求装入背包的最多物品数量。 题目分析 因为我们 只要求装入物品的数量 ,所以 装重的显然没有装轻的划算 。 因此将 数组weight[i]按从小到大排序 , 依次选择每个物品 ,直到装不

    2024年01月17日
    浏览(42)
  • 背包问题分析代码详解【01背包+完全背包+多重背包】

    一、01背包问题 问题描述: 有 N 件物品和一个容量为 V 的背包,每件物品有各自的价值且只能被选择一次,要求在有限的背包容量下,装入的物品总价值最大。 朴素01背包 状态f[i , j]定义:在前i个物品中选,总体积不超过j的价值最大值 状态转移 1) 选第i个物品:f[i,j] = f

    2024年02月06日
    浏览(40)
  • 01背包问题——以小明的背包1 为例

    本文旨在加强01背包问题的记忆与理解,步骤会细化 小明有一个容量为 VV的背包。 这天他去商场购物,商场一共有 N 件物品,第 i 件物品的体积为 w ,价值为 v 。 小明想知道在购买的物品总体积不超过 V 的情况下所能获得的最大价值为多少,请你帮他算算。 输入描述 输入第

    2023年04月14日
    浏览(36)
  • leetcode刷题之背包问题(01背包)

    01 背包 概念:有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是 w e i g h t [ i ] weight[i] w e i g h t [ i ] ,得到的价值是 v a l u e [ i ] value[i] v a l u e [ i ] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。 方法1:暴力回溯法 方法2:动态规划 三个

    2024年02月02日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包