首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

背包查找最大值

背包问题是一种组合优化问题,通常用于解决如何在一个给定容量的背包中放入物品,使得背包中物品的总价值最大。背包问题有很多变种,其中最常见的是0/1背包问题和完全背包问题。

0/1背包问题

在0/1背包问题中,每个物品只能选择一次。给定一组物品,每个物品有一个重量和一个价值,以及一个背包的最大承重。目标是选择一些物品放入背包,使得背包中物品的总价值最大,同时不超过背包的最大承重。

动态规划解法

可以使用动态规划来解决0/1背包问题。定义一个二维数组dp,其中dp[i][w]表示在前i个物品中选择,总重量不超过w的情况下,可以获得的最大价值。

状态转移方程为:

代码语言:javascript
复制
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]) if weight[i] <= w
dp[i][w] = dp[i-1][w] if weight[i] > w

初始条件为:

代码语言:javascript
复制
dp[0][w] = 0 for all w
dp[i][0] = 0 for all i

最终答案为dp[n][W],其中n是物品的数量,W是背包的最大承重。

完全背包问题

在完全背包问题中,每个物品可以选择无限次。目标同样是选择一些物品放入背包,使得背包中物品的总价值最大,同时不超过背包的最大承重。

动态规划解法

定义一个二维数组dp,其中dp[i][w]表示在前i个物品中选择,总重量不超过w的情况下,可以获得的最大价值。

状态转移方程为:

代码语言:javascript
复制
dp[i][w] = max(dp[i-1][w], dp[i][w-weight[i]] + value[i]) if weight[i] <= w
dp[i][w] = dp[i-1][w] if weight[i] > w

初始条件为:

代码语言:javascript
复制
dp[0][w] = 0 for all w
dp[i][0] = 0 for all i

最终答案为dp[n][W],其中n是物品的数量,W是背包的最大承重。

示例代码(Python)

以下是一个0/1背包问题的示例代码:

代码语言:javascript
复制
def knapsack_01(weights, values, max_weight):
    n = len(weights)
    dp = [[0] * (max_weight + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, max_weight + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]

    return dp[n][max_weight]

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
max_weight = 5
print(knapsack_01(weights, values, max_weight))  # 输出:7
页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

  • 0-1背包问题暴力递归

    给你一系列物品的价值数组和所占背包容量的数组,给你一个有限容量的背包,求能背的背包的最大值,并返回这个最大值。 这里是不能多拿背包的,也就是这里的背包都有且只有一个。 实现如下,首先递归函数的逻辑就是:选择拿不拿当前遍历到的背包,如果拿就要选择加上当前背包的价值,并且把当前背包的所占容量也加上去,在遍历到下一个index,这里index就推动了递归的进行,并且两个终止条件分别代表的意思是如果当前情况下背包已经占有的容量大于了背包的容量,这时候返回一个不成功,此时这个背包在当前情形下是不能有的,返回一个-1,在比大小的时候就自然不会要这条分支,顺水推舟,这个已经占有的容量应该伴随递归函数。process可以理解为index及以后的所有情况的最大值。

    02

    背包问题-动态规划java实现代码

    动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法–动态规划。1957年出版了他的名著《Dynamic Programming》,这是该领域的第一本著作。 动态规划一般可分为线性动规,区域动规,树形动规,背包动规四类。举例:线性动规:拦截导弹,合唱队形,挖地雷,建学校,剑客决斗等;区域动规:石子合并, 加分二叉树,统计单词个数,炮兵布阵等;树形动规:贪吃的九头龙,二分查找树,聚会的欢乐,数字三角形等;背包问题:01背包问题,完全背包问题,多重背包问题,分组背包问题,二维背包,装箱问题,挤牛奶(同济ACM第1132题)等;

    03

    『ACM-算法-动态规划』初识DP动态规划算法

    一、多阶段决策过程的最优化问题 在现实生活中,有类活 动的过程,由于 它的特殊性,可将过程分成若干个互相阶段。在它的每一阶段都需要作出决策,从而使整个过程达到最好的活动效果。当阶段决策的选取不是任意确定的,它依赖于当前面临的状态,又影响以后的发展,当段决策确定后,就组成一个决策序列,因而也就确定了整个过程的一条活动路线,这个问题看作是个前后关联具有链状结构的 多阶段过程就称为多阶段决策过程,这就称为多阶段决策问题。 多阶段决策过程,是指这样的一类特殊的活动过程,问题可以按时间顺序分解互联系的阶段,在每-个阶段都要作出决策,全部过程的决策是-个决策序列。

    02

    01背包问题动态规划

    首先要明确这张表是至底向上,从左到右生成的。 为了叙述方便,用e2单元格表示e行2列的单元格,这个单元格的意义是用来表示只有物品e时,有个承重为2的背包,那么这个背包的最大价值是0,因为e物品的重量是4,背包装不了。 对于d2单元格,表示只有物品e,d时,承重为2的背包,所能装入的最大价值,仍然是0,因为物品e,d都不是这个背包能装的。 同理,c2=0,b2=3,a2=6。 对于承重为8的背包,a8=15,是怎么得出的呢? 根据01背包的状态转换方程,需要考察两个值, 一个是f[i-1,j],对于这个例子来说就是b8的值9,另一个是f[i-1,j-Wi]+Pi; 在这里, f[i-1,j]表示我有一个承重为8的背包,当只有物品b,c,d,e四件可选时,这个背包能装入的最大价值 f[i-1,j-Wi]表示我有一个承重为6的背包(等于当前背包承重减去物品a的重量),当只有物品b,c,d,e四件可选时,这个背包能装入的最大价值 f[i-1,j-Wi]就是指单元格b6,值为9,Pi指的是a物品的价值,即6 由于f[i-1,j-Wi]+Pi = 9 + 6 = 15 大于f[i-1,j] = 9,所以物品a应该放入承重为8的背包 代码:

    03

    ACM一年记,总结报告(希望自己可以走得很远)

    一、 知识点梳理 (一) 先从工具STL说起: 容器学习了:stack,queue,priority_queue,set/multiset,map/multimap,vector。 1.stack: 栈是一种只能在某一端插入和删除数据的特殊线性表。他按照先进先出的原则存储数据,先进的数据被压入栈底,最后进入的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后被压入栈的,最先弹出)。因此栈也称先进后出表。 2.queue: 是典型的先进先出容器,FIFO(first-in-first-out),通俗点说就,这个容器就像是在排队,走的人在前面走,来的人在后面排,排队的顺序和离开的顺序是相同的。 3. priority_queue: 优先队列priority_queue可理解为一个大根堆,有特定权值的先出队,也形象的举个例子,拍卖,无论出手多晚,只要出价足够高,就可以拿走拍卖品。(但是,在优先队列里,元素排列绝对不是完全单调的,只能确定队首元素是最大的,保证出队顺序是单调的) 4.vector: 简单地说,vector是一个能够存放任意类型的动态数组,能够增加和删除数据,可以直接访问向量内任意元素。 5. set/multiset: 两容器相似,但set为有序集合,元素不能重复,multiset为有序多重集合,可包含若干相等的元素,可以放结构体,但是一定要重载排列方式,不然编译都过不了,set的查找于插入元素的复杂度为log(N),是一个比较好用的容器。 PS:但是,在使用结构体时,有几个元素,就要写几个元素的比较,不然会被视为同一个元素: 6.map/multimap:map映射容器的元素数据是由一个Key和一个Value成的,key与映照value之间具有一一映照的关系。map插入元素的键值不允许重复,类似multiset,multimap的key可以重复。比较函数只对元素的key进行比较,元素的各项数据只能通过key检索出来。虽然map与set采用相同的数据结构,但跟set的区别主要是set的一个键值和一个映射数据相等,Key=Value。就好像是set里放的元素是pair组成了map,map的key也可以为自定义数据类型,但是也要像上文set一样写重载函数。 算法(algorithm):在算法头文件下包括了好多函数,下面列出常用的。

    02
    领券