| 【python】一篇讲透背包问题（01背包 完全背包 多重背包 二维费用背包） | 您所在的位置：网站首页 › 菜鸟背包 › 【python】一篇讲透背包问题（01背包 完全背包 多重背包 二维费用背包） |
【python】一篇讲透背包问题（01背包 完全背包 多重背包 二维费用背包）
|
面对背包问题，有一个很重要的方程式：状态转移方程式 所以每一种背包问题我都会给出状态转移方程式 #01背包 什么是01背包型问题？先给大家感受一下01背包型问题： 给定n种物品和一背包。物品i的重量是wi，其价值为ci，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 这种时候面对每一个物品都有两个选择：选还是不选，这就是典型的01背包问题！ 01背包怎么做？既然01背包的核心是拿与不拿，那么就要判断是拿之后总价值高还是不拿的总价值高。当然，拿是有前提的，那就是背包的容量要够！ 背包容量够了，那如何看拿与不拿谁的总价值高呢？ 我们先来看下dp表，就可以一目了然！ 根据上面的推算，得出01背包状态转移方程式： dp[i][j] = max( dp[ i - 1 ][ j ] , dp[ i - 1 ][ j - w[ i ]] + c[ i ]) 实战T大计算机系费尽九牛二虎之力，终于挖来了某系第一肌肉男（从此被称为计算机第0肌肉男）。他平时除了自习，就是看电影。但是即使肌肉男有强大的肌肉，仍然会面临每个月有限的流量耗尽的问题。已知肌肉男的流量p是有限的，现在有某舍友提供的n部最新电影，看每部电影会消耗肌肉男一定的流量，但是也会给肌肉男带来一定的兴奋值。肌肉男想在自己有能力的情况下产生最多的兴奋值，他由于平时忙于上自习，把这个任务交给了你，如果你能完成，他就帮你领一年的外卖哦！ 输入数据第一行有一个数字p，表示肌肉男的流量值；第二行是一个数字n，表示一共有n部电影；以下有n行，每行第一个数表示该电影消耗的流量大小，第二个数表示该电影带给肌肉男的兴奋值。 输出数据只有一行，表示肌肉男所能达到的最大兴奋值。 样例输入 10 4 2 1 3 3 4 5 7 9 样例输出 12 p = int(input()) n = int(input()) lists = [list(map(int,input().split())) for i in range(n)] # lists[0]为所需流量 lists[1]为兴奋值 # print(lists) dp = [[0]*(p+1) for _ in range(n+1)] for i in range(1,n+1): for j in range(1,p+1): if lists[i-1][0] |
图片中的 1 是背包容量为（5-3）的最大价值，5是当前背包容量，为了在书包里边放下2号物品（也就是所需容量为 3 ），所以要给该物品腾出 3 的位置。【本文地址】