背包_牛客博客

动态规划

参考网上内容侵删
动态规划（ Dynamic Programming, DP）是最优化问题的一种解决方法，本质上状态空间的状态转移。所谓状态转移是指每个阶段的最优状态（对应于子问题的解）可以从之前的某一个或几个阶段的状态中得到，这个性质叫做最优子结构。而不管之前这个状态是如何得到的，这被称之为无后效性。

大问题的最优解可以由小问题的最优解得到
不关心小问题最优解中自变量的取值（因变量是最优化的变量）

背包九讲

01背包

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

满足容量限制的条件下，使得价值最大化

用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值；则其状态转移方程：

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

背包问题核心

f[j] = max(f[j],f[j-c[i]]+V[i])

01背包：（每种物品就有一个）

C = [3,2,6,7,1,4,9,5]#cost 单个物品所占容量
V = [6,3,5,8,3,1,6,9]#每个物品的价值
target = 15 #背包容量
F = [0 for i in range(0,target+1)] #初始化 元素个数为背包大小加1（target+1）
n = len(C)

def ZeroOneBackPack(cost,value):
    for i in reversed(range(cost,target+1)): #逆序遍历
        F[i] = max(F[i],F[i-cost]+value)

for i in range(0,n):
    ZeroOneBackPack(C[i],V[i])
print (F[target])

完全背包：（每种物品有无数多个）

C = [3,2,6,7,1,4,9,5]
V = [6,3,5,8,3,1,6,9]
target = 15
F = [0 for i in range(0,target+1)]
n = len(C)

def CompleteBackPack(cost,value):
    for i in range(cost,target+1):#这是和01背包唯一的区别 正序遍历
        F[i] = max(F[i],F[i-cost]+value)

for i in range(0,n):
    CompleteBackPack(C[i],V[i])
print (F[target])

多重背包：（每种物品有有限个，并通过数组给出。）

时间优化算法对于个数较多的物品进行捆绑，变成多种物品，如果某种物品有9个，可以转化为没1，2，4个进行捆绑产生3种物品一共7个，剩下的2个单独算，三种物品C，V分别乘以捆绑个数如：（C，V），（2C，2V），（4C，4V）

C = [3,2,6,7,1,4,9,5]
V = [6,3,5,8,3,1,6,9]
Count = [3,5,1,9,3,5,6,8]#每种物品的实现
target = 20
F = [0 for i in range(0,target+1)]
n = len(C)

def CompleteBackPack(cost,value):
    for i in range(cost,target+1):
        F[i] = max(F[i],F[i-cost]+value)

def OneZeroBackPack(cost,value):
    for i in reversed(range(cost,target+1)):
        F[i] = max(F[i],F[i-cost]+value)

def MultipleBackPack(cost,value,count):
        if (cost * count) >= target:#当该种物品的个数乘以体积大于背包容量，视为有无限个即完全背包
            CompleteBackPack(C[i],V[i])
            return
        
        temp_count = 1  #以上情况不满足，转化为以下情况，具体参考《背包九讲》多重背包的时间优化
        while(temp_count<count):
            OneZeroBackPack(temp_count*cost,temp_count*value)
            count = count - temp_count
            temp_count = temp_count * 2  #转化为1，2，4
        OneZeroBackPack(count*cost,count*value)#9个中剩下两个

for i in range(0,n):
    MultipleBackPack(C[i],V[i],Count[i])
print (F[target])

二维背包：

相比前三种，二维背包有两种Cost C1和C2和两个背包容量target1，target2，代码上多了一层内循环，状态上多了一维（F[][])，根据物品的个数选择是01背包（逆序遍历）完全背包（正序遍历）。以下的代码中每种物品只有一个，所以子问题为01背包

C1 = [3,2,6,7,1,4,9,5]
C2 = [6,2,4,6,7,3,8,5]
V = [6,3,5,8,3,1,6,9]

#Count = [3,5,1,9,3,5,6,8]
target1 = 20
target2 = 25
n = len(C1)
F = [[0] * (target2+1) for i in range(0,target1+1)]
for i in range(0,n):
    for j in reversed(range(C1[i],target1+1)):
        for m in reversed(range(C2[i],target2+1)):#逆序遍历
            F[j][m] = max(F[j][m],F[j-C1[i]][m-C2[i]] + V[i])

print (F[target1][target2])

搜索还是DP?

在看到一道背包问题时，应该用搜索还是动态规划呢？

首先，可以从数据范围中得到命题人意图的线索。如果一个背包问题可以用DP解，V一定不能很大，否则O(VN)的算法无法承受，而一般的搜索解法都是仅与N有关，与V无关的。

V很大时（例如上百万），命题人的意图就应该是考察搜索。
N较大时（例如上百），命题人的意图就很有可能是考察动态规划了。

N小可以搜索，N大不能搜索

另外，当想不出合适的动态规划算法时，就只能用搜索了。例如看到一个从未见过的背包中物品的限制条件，无法想出DP的方程，只好写搜索以谋求一定的分数了。