DP之0-1背包问题

0-1背包问题是指每一种物品都只有一件，可以选择放或者不放。现在假设有N件物品，背包承重为M。

对于这种问题，我们可以采用一个二维数组去解决：f[i][j]，其中i代表加入背包的是前i件物品，j表示背包的承重，f[i][j]表示当前状态下能放进背包里面的物品的最大总价值。那么，f[N][M]就是我们的最终结果了。

采用DP，必须要知道初始状态和状态转移方程。初始状态很容易就能知道，那么状态转移方程如何求呢？对于一件物品，我们有放进或者不放进背包两种选择：

  （1）假如我们放进背包，f[i][j] = f[i - 1][j - weight[i]] + value[i]，这里的f[i - 1][j - weight[i]] + value[i]应该这么理解：在没放这件物品之前的状态值加上要放进去这件物品的价值。而对于f[i - 1][j - weight[i]]这部分，i - 1很容易理解，关键是 j - weight[i]这里，我们要明白：要把这件物品放进背包，就得在背包里面预留这一部分空间。

  （2）假如我们不放进背包，f[i][j] = f[i - 1][j]

    因此，我们的状态转移方程就是：f[i][j] = max(f[i][j] = f[i - 1][j] , f[i - 1][j - weight[i]] + value[i])  

    当然，还有一种特殊的情况，就是背包放不下当前这一件物品，这种情况下f[i][j] = f[i - 1][j]。

Python代码：

# -*- coding: utf-8 -*-
"""
Created on Wed Aug 29 15:50:45 2018
@author: Administrator
"""
def BagOf01(N, M, weight, values):#DP
    #f = [[0]*(M+1)]*(N+1)
    f=[[0 for j in range(M+1)] for i in range(N+1)]#这样写
    for i in range(1, N+1):#i:物品数,j:背包容量
        for j in range(1,M+1):
            if j < weight[i-1]:
                f[i][j] = f[i-1][j]
            else:
                f[i][j] = max(f[i-1][j],f[i-1][j-weight[i-1]] + values[i-1])
    x = [False for i in range(N)]
    j = M
    for i in range(1,N+1):
        if f[i][j] > f[i-1][j]:
            x[i-1] = True
            j -= weight[i-1]
    for i in range(N):
        if x[i]:
            print('the choosing num is:',i)
    return f[N][M]
if __name__ == '__main__':
    N = int(raw_input())#个数
    M = int(raw_input())#容量
    weight = [i for i in raw_input().split()]
    weight = map(int,weight)
    values = [j for j in raw_input().split()]
    values = map(int,values)
    res = BagOf01(N, M, weight, values)
    print(res)

此外还有完全背包和多重背包问题，具体见：https://www.cnblogs.com/fengziwei/p/7750849.html