背包型动态规划——背包问题3

傷城~ 2022-10-27 12:06 171阅读 0赞

#  #

给定 `n` 种物品, 每种物品都有无限个. 第 `i` 个物品的体积为 `A[i]`, 价值为 `V[i]`.

再给定一个容量为 `m` 的背包. 问可以装入背包的最大价值是多少?

**样例 1:**

输入: A = [2, 3, 5, 7], V = [1, 5, 2, 4], m = 10
    输出: 15
    解释: 装入三个物品 1 (A[1] = 3, V[1] = 5), 总价值 15.

**样例 2:**

输入: A = [1, 2, 3], V = [1, 2, 3], m = 5
    输出: 5
    解释: 策略不唯一. 比如, 装入五个物品 0 (A[0] = 1, V[0] = 1).

### 1、题目分析 ###

我的理解这个问题和[背包问题5][5]类似，只不过同样是将重量改为了价值。

因此假设设f\[i\]\[w\] 表示 用前i个物品拼出重量w时最大总价值

### 2、代码实现 ###

class Solution:
        """ @param A: an integer array @param V: an integer array @param m: An integer @return: an array """
        def backPackIII(self, A, V, m):
            # write your code here
            if len(V)==0 or m==0 or len(A)==0:
                return 0
            dp=[0]*(m+1)
            for i in range(1,m+1):
                for j in range(len(A)):
                    if i>=A[j]:
                        dp[i]=max(dp[i],dp[i-A[j]]+V[j])#注意对比与背包问题5的区别
            return dp[m]

#  #

[5]: https://editor.csdn.net/md?articleId=113620753

发表评论取消回复

表情：

评论列表（有 0 条评论，171人围观）

还没有评论，来说两句吧...

相关阅读

相关动态规划-背包问题

动态规划--背包问题

悠悠/ 2024年04月23日 20:02/ 0 赞/ 81 阅读

相关背包型动态规划装箱问题

题目描述 Description 有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）。要求n个物品中，任

秒速五厘米/ 2024年02月17日 19:24/ 0 赞/ 62 阅读

相关背包问题-动态规划

[背包问题九讲][Link 1] [背包问题参考博客][Link 2] 文章目录介绍: 背包问题 01背包问题

逃离我推掉我的手/ 2023年08月17日 17:42/ 0 赞/ 112 阅读

相关背包型动态规划——背包问题6

给出一个都是正整数的数组 `nums`，其中没有重复的数。从中找出所有的和为 `target` 的组合个数。示例：输入: nums = [1, 2, 4

阳光穿透心脏的1/2处/ 2022年10月27日 12:06/ 0 赞/ 162 阅读

相关背包型动态规划——背包问题3

给定 `n` 种物品, 每种物品都有无限个. 第 `i` 个物品的体积为 `A[i]`, 价值为 `V[i]`. 再给定一个容量为 `m` 的背包. 问可以装入背包的

傷城~/ 2022年10月27日 12:06/ 0 赞/ 172 阅读

相关背包型动态规划——背包问题5

给出 n 个物品, 以及一个数组, `nums[i]` 代表第i个物品的大小, 保证大小均为正数, 正整数 `target` 表示背包的大小, 找到能填满背包的方案数。

素颜马尾好姑娘i/ 2022年10月27日 12:06/ 0 赞/ 182 阅读

相关背包型动态规划——背包问题1

在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A\[i\] 示例：样例 1: 输入: [3,4,8,5]

旧城等待，/ 2022年10月27日 06:30/ 0 赞/ 153 阅读

相关背包型动态规划——背包问题2

有 `n` 个物品和一个大小为 `m` 的背包. 给定数组 `A` 表示每个物品的大小和数组 `V` 表示每个物品的价值. 问最多能装入背包的总价值是多大? 样例

忘是亡心i/ 2022年10月27日 06:29/ 0 赞/ 153 阅读

相关背包问题，动态规划

将下面四个重量的物品1，2，2，3 价值分别是9，3，3，6 装进重量为4的背包中，使得背包的重量不超过4，并且价值最大。 include<iostream>

左手的ㄟ右手/ 2022年02月28日 14:50/ 0 赞/ 295 阅读

相关动态规划背包问题

[本篇博文参考此博文，该博文PPT非常有助理解][PPT] > 问题描述： > 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背

傷城~/ 2021年09月11日 08:42/ 0 赞/ 420 阅读