关键词：
背包问题（0-1背包问题）
假设你是个小偷，背着一个可装 4 磅东西的背包。 你可盗窃的商品有如下3件（摘自算法图解）：
作为一名优秀的小偷，为了让盗窃的商品价值最高，该选择哪些商品呢？
很明显，小偷需要在满足背包容量要求下，选择价值总和最大的。
使用动态规划
先解决小背包（子背包）问题，再逐步解决原来的问题
-
状态转移
cell[i][j]表示前i种物品恰放入一个容量为j的背包能获得的最大价值
coding
def knapsack(goods,volume):
dp = [[0]*(volume+1) for _ in range(len(goods))]
for j in range(1,volume+1):#初始化
if goods[0][1] <= j:
dp[0][j] = goods[0][0]
for i in range(1,len(goods)):
for j in range(1,volume+1):
if goods[i][1] <= j:
dp[i][j] = max(dp[i-1][j],goods[i][0]+dp[i-1][j-goods[i][1]])
else:
dp[i][j] = dp[i-1][j]
return dp
goods = [[1500,1],[3000,4],[2000,3]]#价值 重量
volume = 4
knapsack(goods,volume)
结果
将吉他和笔记本电脑装入背包时价值最高，为3500美元。
在刚才的盗窃活动中，每次可以偷的东西都是一个完整的个体，对每个物品要么选择偷，要么不偷，所以称为 0-1背包问题
可以偷商品的一部分吗（完全背包问题）
假如你在杂货店行窃，可偷成袋的扁豆和大米，但如果整袋装不下，可打开包装，再将背包 倒满。在这种情况下，不再是要么偷要么不偷，而是可偷商品的一部分。如何使用动态规划来处 理这种情形呢？
假设有如下商品（每种商品无限多）可供选择。
略作思索，小偷发现在决定偷哪些东西时， 动态规划 是一个不错的方法，因为：
从每种物品i 偷/不偷 ((k_i in 0,1))变为 偷多少单位 ((k_iin 0,1,2,...,W/w_i))，背包总容量 W，第i类物品占 (w_i) 的空间。
-
状态转移
[cell[i][j] = max(cell[i-1][j],v[i]*k_i+cell[i-1][j-k_i*w[i]])\k_iin 0,1,2,...,W/w_i ]
coding
def knapsack(w,v,volume):
dp = [[0]*(volume+1) for _ in range(len(w))]
for j in range(1,volume+1):
for k in range(j//w[0]+1):
dp[0][j] = max(dp[0][j],v[0]*k)
for i in range(1,len(w)):
for j in range(1,volume+1):
temp = 0
for k in range(j//w[i]+1):
temp = max(temp,v[i]*k+dp[i-1][j-k*w[i]])
dp[i][j] = max(dp[i-1][j],temp)
return dp
weight = [2,1,3] #重量
value = [5,2,4]#价值
volume = 7
knapsack(weight,value,volume)
结果
物以稀为贵（多重背包问题）
由于燕麦的营养价值比较高，所以只有一点点，可偷的商品受到了限制
每种商品只有部分可供选择 (k_i<M_i)，但问题还是
偷多少单位 ((k_iin 0,1,2,...,W/w_i))，背包总容量 W，第i类物品占 (w_i) 的空间。
多重背包问题 相比 完全背包问题多了限制条件，即可偷物品的数量。
同样使用动态规划
- 状态转移[cell[i][j] = max(cell[i-1][j],v[i]*k_i+cell[i-1][j-k_i*w[i]])\k_iin 0,1,2,...,W/w_i,k_i leq M_i ]
coding
def knapsack(w,v,M,volume):
dp = [[0]*(volume+1) for _ in range(len(w))]
for j in range(1,volume+1):
for k in range(min(j//w[0],M[0])+1):#增加限制条件
dp[0][j] = max(dp[0][j],v[0]*k)
for i in range(1,len(w)):
for j in range(1,volume+1):
temp = 0
for k in range(min(j//w[i],M[i])+1):#增加限制条件
temp = max(temp,v[i]*k+dp[i-1][j-k*w[i]])
dp[i][j] = max(dp[i-1][j],temp)
return dp
weight = [2,1,3] #重量
value = [5,2,4] #价值
maxk = [1,3,3] #数量
volume = 7
knapsack(weight,value,maxk,volume)
结果
sh我真棒.bashrc-随意偷东西(代码片段)
0-1背包问题贪心算法动态规划(代码片段)
...vi元，重wi磅，此处vi与wi都是整数。他希望带走的东西越值钱越好，但他的背包中至多只能装下W磅的东西，W为一整数。应该带走哪几样东西？这个问题之所以称为0-1背包，是 查看详情
优化算法系列-模拟退火算法——0-1背包问题(代码片段)
...品价值vi元，重wi磅，其中vi、wi都是整数。他希望带走的东西越值钱越好，但他的背包小，最多只能装下W磅的东西（W为整数）。如果每件物品或被带走或被留下，小偷应该带走哪几件东西？ 2解空间设xi表示第i件物品的... 查看详情
01背包问题和完全背包问题(代码片段)
...体积为weight[i]，价值为value[i]，现在往背包里面装东西，怎么装能使背包的内物品价值最大？看到这个问题，可能会想到贪心算法& 查看详情
背包问题找物品(代码片段)
...牌。从那时起，艾迪发现物理学实际上是竞赛中最重要的东西。因此，他想组建一个团队来指导接下来的选手去征服PACM比赛(PACM是物理、算法、编码、数学的简称)。有 查看详情
动态规划之01背包问题(代码片段)
...种风格的描述：假设你是一个小偷，背着一个可装下4磅东西的背包，你可以偷窃的物品如下：为了让偷窃的商品价值最高，你该选择哪些商品？暴力解法最简单的算法是：尝试各种可能的商品组合，并找出价值最高的组合。这... 查看详情
————2020.1.17————(代码片段)
...背包。 何谓0-1背包，可以这样想，那里有一堆值钱的东西，每一样东西只有一件，他们的价值和体积都不一样，现在要你从这n件里面挑选一些放到一个容量一定的背包里面，使得你的背包里的东西总价值最大。对于这些东... 查看详情
nyoj49-开心的小明(动态规划，0-1背包问题)(代码片段)
...元钱就行”。今天一早小明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是 查看详情
题解「luogup1064」金明的预算方案(代码片段)
...最大价值。然后得出状态转移方程：如果可选(即把这个东西放进去 查看详情
背包问题(代码片段)
背包问题分类：0-1背包（每种物品只有一个）完全背包（每种物品无限多）多重背包（每种物品Mi个，0-1背包算是多重背包的特殊情况）混合背包。。。解决此类问题主要将其转化为0-1背包的问题&#x... 查看详情
背包问题（贪心策略）(代码片段)
原创给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?物品时可以拆分的，比如可以将物品的三分之一放入背包。使用优先放入【价值/重量... 查看详情
动态规划问题3--多重背包(代码片段)
多重背包问题描述及其代码在01背包的基础上，01背包是每个物品有一个，所以只能放入一次，此时我们再加入一个物品个数的数组s,表示每个物品的个数，多重背包介于01背包和完全背包中间，加入了判断物品个数的一个维度，... 查看详情
动态规划问题3--多重背包(代码片段)
多重背包问题描述及其代码在01背包的基础上，01背包是每个物品有一个，所以只能放入一次，此时我们再加入一个物品个数的数组s,表示每个物品的个数，多重背包介于01背包和完全背包中间，加入了判断物品个数的一个维度，... 查看详情
混合背包问题(代码片段)
原题链接如果s为0，那么是完全背包问题，用完全背包的方法求解如果s为-1，那么是01背包问题，把它当做数量为1的特殊的多重背包（其实它就是特殊的多重背包问题）s为某个数，那么就是普通的多重... 查看详情
动态规划-背包问题(代码片段)
背包问题是一种组合优化的NP完全问题。有N个物品和容量为W的背包，每个物品都有自己的体积w和价值v，求拿哪些物品可以使得背包所装下的物品的总价值最大。如果限定每种物品只能选择0个或1个，则问题称为0-1背... 查看详情
在windows家里杀死一个偷端口的家伙
...有代码整体的逻辑有点问题，于是就review了代码，改了些东西，然后再次启动服务，但是，问题来了：Addressalreadyinuse:JVM_Bind 好办，找任务管理器杀掉不该有的进程，过程全靠猜，杀了几个，再次启动后，成功！ 如果世... 查看详情
什么是算法？从枚举到贪心再到启发式（上）(代码片段)
...一个问题，得想想办法来解决它！在此之前我们再讲一点东西，观察上面的问题，能发现什么特点呢？一般而言，算法所需要解决的问题，都能分成两个部分：目标：什么是目标呢？简单点说就是要优化的东西，比如在上述背包... 查看详情
算法背包问题(代码片段)
...的满足感最高。当时一下没想出来，后来一想，这不就是背包问题吗？所以这里整理一下背包问题的算法。--------------------------------------------------------------------------------------- 查看详情