加油

# 0 - 1背包问题详解
    
    # 问题描述：
    '''
    有一组不同重量，不可分割的物品，每种物品有且仅有一个
    每个物品都有对应的价值，我们需要选择一些物品放入背包
    在满足背包最大承重的前提下，使得放入物品的价值最大
    '''
    
    object_numbers, bag_wight = map(int, input().split())
    
    w = []
    v  = []
    
    for obj in range(object_numbers):
        obj_weight, obj_value = map(int, input().split())
        w.append(obj_weight)
        v.append(obj_value)
    
    # print(w)
    # print(v)
    
    # 动态规划
    # 1：定义数组dp[i][j]: 当物品个数为i, 背包承重为j时可以装入的最大的价值
    dp = [ [0 for j in range(bag_wight + 1) ] for i in range(object_numbers + 1) ]
    
    # 获得转换函数
    # if 物品个数为0 或者 背包承重为0------> return 0
    # if 物品的重量 > 当前背包的剩余容量 ----> return dp[i - 1, w] # 不将这个物品放入背包，背包的最大的容量 = 没有i - 1件物品时的容量
    # if 物品的重量 <= 当前背包的剩余容量 ---> return max(将这个物品放入背包max_value[i - 1, w - wi] + vi， 不放 dp[i - 1, w])
    for i in range(1, object_numbers + 1):
        for j in range(1, bag_wight + 1):
            dp[i][j] = dp[i - 1][j]
            if j >= w[i - 1]:
                dp[i][j] = max( dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1] )
    # print(dp)
    print(dp[object_numbers][bag_wight])

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

加油

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

用筛法求之N内的素数。（C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

蓝桥杯算法提高VIP-01背包-题解(Python代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C二级辅导-同因查找（C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言训练-求函数值（C语言代码）

【亲和数】（C语言代码）

妹子杀手的故事（C语言代码）

【偶数求和】（C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

A+B for Input-Output Practice (VI) （C语言代码）

2^k进制数（C语言描述，蓝桥杯）

加油