0-1背包问题

来源

已知 n个物体1,2,3,…,n与一个背包。物体i的重量为Wi>0，价值为 Pi>0(i=1,2,3,…,n)，背包容量为M>0。

求在不超过背包容量的情况下，使得装进去的物体的价值最高。

输入格式
第一行为一个正整数T，表示有几组测试数据。

每组测试数据的第一行为两个整数n和M,0<n<20,0<M<100000。

再下去的n行每行有两个整数Wi, Pi,0<Wi,Pi<10000。

输出格式
对于每组测试数据，输出一行，只含一个整数，表示装进去物体的价值最高值。

样例

#input
1
5 10
2 6
2 3
6 5
5 4
4 6

#output
15

思路：

1.背包问题也是动态规划问题，这里的dp应考虑的是二维形式，dp[i][j] 表示的是从物品[0-i]中任意取出放进容量为j的背包里，价值总和最大为dp[i][j],注意这里是物品[0-i]不是物品i。

2.知道了dp的含义，就应该考虑初始化问题，因为dp[i][j]，在i,j>0时都是由前一状态推导所得所以这里也应知道dp[i][j]分别在i=0和j=0的状态值，易知，i=0时，也就是dp[0][j]，背包存放编号为0的物品时候的最⼤价值，当j<W0时，也就是背包比物品重量轻时为dp[0][j]=0，否则为物品本身的价值。dp[i][0]则表示背包承重为0时⽆论是取哪些物品，背包价值总和⼀定为0。

3.推导公式：
dp[i][j]是由两个方向推导获得：
1）dp[i - 1][j]推出，即当背包容量为j<当前物品i的重量时，⾥⾯放不下物品i，那么最大价值还是处于上一个状态，即dp[i][j]=dp[i - 1][j]；
2）当背包容量为j>=当前物品i的重量时,这时问题就转换为背包容量M在放物品i的前提下，剩下的M-Wi的容量,在物品[0,i-1]中所能获得的最大价值dp[i-1][j-Wi]，总价值就为：dp[i-1][j-Wi]+Pi

所以总的来说，dp[i][j]= max(dp[i - 1][j], dp[i - 1][j-Wi]+Pi)

python实现

t = int(input())
for x in range(t):
        n,M = map(int,input().split())
        L = []
        for i in range(0,n):
            ni = list(map(int,input().split()))
            L.append(ni)

        dp = [[0 for j in range(M+1)] for i in range(n)]
        for i in range(n):
            dp[i][0] = 0
        for j in range(M+1):
            if j< L[0][0]:
                dp[0][j] = 0
            else:
                dp[0][j] = L[0][1]


        for i in range(1,n):
            for j in range(1,M+1):
                if j<L[i][0]:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-L[i][0]]+L[i][1])
        print(dp[n-1][M])

这里仅供自己复习使用，也欢迎批评指正。