苏苏酱陪你学动态规划（三）——背包问题

清疚 2022-03-12 11:30 198阅读 0赞

## 1、0-1背包问题 ##

背包问题的典型描述如下：

一、假如你是奥特曼，有N点的攻击力，现在有一些小怪兽，每一个小怪兽被打倒都需要消耗你一定数量的攻击力，同时你将获得该怪兽对应的金币。现在请计算你所能获得的最多金币数。

二、加入你是小偷，带了一个容量为V的包，此时你去商店偷商品（每一个商品都具有不同的价值），每偷一个商品将占用你背包一定的空间，请你偷价值尽量多的商品。

## 2、问题的分析 ##

这一类问题都是0-1背包问题，换句话说，每一个问题中都可以抽象为“偷”或者“不偷”，以此来达到目标函数最大化。这种问题的求解通常使用动态规划。

假设已知x个商品它们的体积存储在数组L中；

假设已知x个商品它们的价值存储在数组P中；

假设背包最大容积是V，那么我们的状态函数就是B(x,V)——表示从x个商品中偷使得获得价值最多，此时的背包容积为V。

现在我们可以从后往前推：

如果最后一个商品可以被偷（包还装得下），那么一定偷这个商品（多偷一个是一个，这是常识）

如果最后一个商品的体积大于背包剩下的容积，显然我们已经无法偷这个商品，那么此时的状态函数为B(x-1,V)

现在剩下一个新的问题，那就是剩下的倒数第二个商品是偷好，还是不偷好，也就是偷和不偷哪个可以使最终的收益最大？

一、偷，那么此时的状态函数为B(x-1,V-L\[x-1\])+P\[x-1\]

二、不偷，那么此时的状态函数B(x-1,V)

因此，通过上述分析，我们就知道了状态的转移函数，那么一直运算到边界条件，就可以返回求出最优解，这是动态规划中典型的分而治之的思想，也就是把大问题分解成若干小问题求解，最终获得最优解。

为了避免同一个子问题的反复求解，我们一般使用记忆化递归的方法，记录每一个子问题的解，然后记录在一个数组中，这样可以控制算法的时间空间复杂度。

## 3、编程实现 ##

loupan, zijin = map(int,input().split())
    L = [0]
    P = [0]
    for i in range(loupan):
        l, p = map(int,input().split())
        L.append(l)
        P.append(p)
    B = [[0]*(zijin+1)]*(loupan+1)
    print("B:",B)
    print("L:",L)
    print("P:",P)
    for c in range(1,loupan+1):
        for r in range(1,zijin+1):
            if r < L[c]:
                B[c][r] = B[c-1][r]
            else:
                B[c][r] = max(B[c-1][r],B[c-1][r-L[c]] + P[c])
    print(B[loupan][zijin])

发表评论取消回复

表情：

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

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

相关阅读

相关动态规划-背包问题

动态规划--背包问题

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

相关背包问题-动态规划

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

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

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

背包问题 -------------------- 目录 1. 概述 2. 背包问题：在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个

叁歲伎倆/ 2023年06月30日 08:58/ 0 赞/ 67 阅读

相关苏苏酱陪你学动态规划（一）——股票买卖

1、问题描述给你一串数字，表示每天的股票价格，你在某一天买进，并在未来的某一天卖出，请求出最大的利润值。例： 1，2，6，4，3 那么应该在第一天买进，第三天卖

叁歲伎倆/ 2022年04月18日 04:07/ 0 赞/ 133 阅读

相关苏苏酱陪你学动态规划，拿名企offer

转眼间我已经是一名研三的老学长，时间飞快，感谢互联网知识社区在我成长中给我的帮助。没有互联网社区的知识共享，很多知识我也难以快速了解；没有互联网社区的知识共享，我也不会发现原来

亦凉/ 2022年04月18日 03:19/ 0 赞/ 150 阅读

相关苏苏酱陪你学动态规划（二）——合唱团

1、问题重述有 n 个学生站成一排，每个学生有一个能力值，牛牛想从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 k 个学生

桃扇骨/ 2022年04月16日 04:29/ 0 赞/ 186 阅读

相关【动态规划】三种背包问题（01背包、完全背包、多重背包）

一、01背包问题描述：给定n个物体（它们的重量为：w1，w2，......，wn，价值为：v1，v2，......，vn）和一个承受重量为W的背包，问怎么选取这些物

旧城等待，/ 2022年04月03日 04:09/ 0 赞/ 835 阅读

相关苏苏酱陪你学动态规划（三）——背包问题

1、0-1背包问题背包问题的典型描述如下：一、假如你是奥特曼，有N点的攻击力，现在有一些小怪兽，每一个小怪兽被打倒都需要消耗你一定数量的攻击力，同时你将获得该怪兽对

清疚/ 2022年03月12日 11:30/ 0 赞/ 199 阅读

相关背包问题，动态规划

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

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

相关动态规划背包问题

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

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