欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

编程题之背包问题

程序员文章站 2022-07-15 18:47:58
...

01背包问题

编程题之背包问题

# 示列 1
# 输入
"""
5 10
8 6
10 4
4 2
5 4
5 3
"""
# 输出
"""
19
"""
# 示列 2
# 输入
"""
1 1
10 2
"""
# 输出
"""
0
"""

代码

# 01背包模板题
def solve(weight,value, n, m):
    #
    dp = [[0]*(m+1) for _ in range(n+1)]

    for i in range(1,n+1):
        for j in range(1,m+1):
            if j-weight[i-1]>=0:
            	# 不选当前商品,选当前商品
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i-1]]+value[i-1])
            else:
                dp[i][j] = dp[i-1][j]
    print(dp[-1][-1])


    # 优化
    dp = [0] * (m + 1)
    # weight代表物品的重量
    # value代表物品的价值
    for i in range(1, len(value)+1):
        for j in range(m, 0, -1):
            if j-weight[i-1]>=0:
                dp[j] = max(dp[j],dp[j-weight[i-1]]+value[i-1])

    print(max(dp))
    print(dp[m])


if __name__ == '__main__':
    n, m = map(int, input().split())
    weight = []
    value = []
    for _ in range(n):
        v, w = list(map(int, input().split()))
        weight.append(w)
        value.append(v)
    solve(weight, value, n, m)
相关标签: 数据结构与算法