背包问题

[编程题]背包问题

热度指数：4786 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

有N件物品和一个容量为V的背包。第i件物品的价值是C[i]，重量是W[i]。求解将哪些物品装入背包可使价值总和最大。

输入描述:

输入第一行数 N V (1 <=N <=500) (1<= V <= 10000)

输入 N行 两个数字 代表 C W (1 <= C <= 50000, 1 <= W <=10000)

输出描述:

输出最大价值

示例1

输入

输出

示例2

输入

1 1
10 2

输出

算法知识视频讲解

Python

笑话啊

(30ms) 动态规划 + 压缩状态 + 遍历优化

时间: O(容量 * 物品数)

空间: O(容量)

import sys
# n: 物品数量  cap: 背包容量
n, cap = list(map(int, input().split()))

# values: 物品价值   weights: 物品重量
values, weights = [], []
for _ in range(n):
    v, c  = list(map(int, input().split()))
    values.append(v); weights.append(c)

# 初始化 dp
dp = [values[0] if c >= weights[0] else 0 for c in range(cap)]
# 迭代 dp
for i in range(n):
    for c in range(cap-1,weights[i]-1, -1):
        dp[c] = max(dp[c], dp[c - weights[i]] + values[i])
print(dp[-1])

编辑于 2023-03-24 17:10:57 回复(0)

Python

臆想者

# python版递归解法
n, v = map(int, input().split())
C , W = [], []
for i in range(n):
    c, w = map(int, input().split())
    C.append(c)
    W.append(w)
total = 0
maxval = 0
def dfs(v, C, left):
    global maxval
    global total
    if left==[]&nbs***bsp;min(left)>v:
        if maxval>total:
            total = maxval
        return
    for i in range(len(left)):
        if left[i]<=v:
            v-=left[i]
            maxval+=C[i]
            temp_left = left[:]
            temp_C = C[:]
            temp_left.pop(i)
            temp_C.pop(i)
            dfs(v, temp_C, temp_left)
            maxval-=C[i]
            v+=left[i]
dfs(v, C[:], W[:])
print(total)

发表于 2022-08-12 15:16:05 回复(0)