动态规划-神奇的口袋V2

神奇的口袋:有一个神奇的口袋，总的容积是40，用这个口袋可以变出一些物品，这些物品的总体积必须是40。? John现在有n（1≤n ≤ 20）个想要得到的物品，每个物品的体积分别是a1，a2 ……an 。John可以从这些物品中选择一些，如果选出的物体的总体积是40，那么利用这个神奇的口袋，John就可以得到这些物品。现在的问题是，John有多少种不同的选择物品的方式。输入:输入的第一行是正整数n (1 <= n <= 20)，表示不同的物品的数目。接下来的n行，每行有一个1到40之间的正整数，分别给出a1，a2 ……an 的值。输入样例      输出样例3             3202020动态规划实现：递归实现当数据量过大，运行时间过长，dp的方式实现，运行速度相对较快。i--剩余体积数 j--表示所选择的物品dp[i][j] = dp[i][j-1] + dp[i-nums[j]][j-1]比如求dp[1][1]，dp[20][1]，dp[30][3]，dp[20][2]，dp[10][1]等等，其实最终都是为了实现求dp[40][1],dp[40][2],dp[40][3]，因为求它们的值需要前面的值，这就是dp[40][3]就是求，从3个物品中，找出能凑够40有几种方法，那么dp[40][3] = dp[40][2]+dp[40-nums[3]][2]dp[40][2] = 1,dp[40-nums[3]][2] = 2所以dp[40][3]=3输入样例      输出样例3             3202020dp[][]二维数组的值如下：[[1, 1, 1, 1],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 1, 2, 3],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0],[0, 0, 1, 3]]python算法：

def main():
    N = int(input())
    # dp[i][j]表示从前j种物品里凑出体积i的方法数
    dp = [[0] * (N+1) for i in range(41)]
    # 表示体积数刚巧用完，物品也刚好用完，算1种方法
    dp[0][0] = 1
    nums = []
    for j in range(1,N+1):
        nums.append(int(input()))
        # 0表示刚好用完体积数40，所以无论j的值多少，都算1种方法
        dp[0][j] = 1
    # 为了从序号1开始计算方便，在list0位置增加一个0无意义的数字
    nums.insert(0,0)
    for i in range(1,41):
        for j in range(1,N+1):
            # 表示没有选择该物品
            dp[i][j] = dp[i][j-1]
            # 如果剩余的体积数>=所选择物品的体积数，才能选择
            if i-nums[j] >= 0:
                dp[i][j] += dp[i-nums[j]][j-1]

    print("有%d种不同的选择物品的方式!"%dp[-1][-1])


if __name__ == ‘__main__‘:
    main()