5. 多重背包问题 II(背包模型+二进制优化)
二进制 优化 模型 II 背包 多重 问题
2023-09-14 09:14:58 时间
蓝桥杯国赛指南,详情见专栏
Question
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。
接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数,表示最大价值。
数据范围
0<N≤1000
0<V≤2000
0<vi,wi,si≤2000
提示:
本题考查多重背包的二进制优化方法。
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例:
10
Ideas
时间复杂度:O(N^2*logN)
Code
# 二进制优化O(N*V*logs)
N = 12010
f = [0 for i in range(N)]
w = [0 for i in range(N)]
v = [0 for i in range(N)]
n,m = list(map(int,input().strip().split()))
cnt = 0
for i in range(n):
vi,wi,si = list(map(int,input().strip().split()))
k = 1
while k <= si:
cnt += 1
v[cnt] = k*vi
w[cnt] = k*wi
si -= k
k *= 2
if si > 0:
cnt += 1
v[cnt] = si*vi
w[cnt] = si*wi
n = cnt
for i in range(1,n+1):
for j in range(m,v[i]-1,-1):
f[j] = max(f[j],f[j-v[i]]+w[i])
print(f[m])
相关文章
- js发送和接收二进制字节流数据
- (剑指Offer)面试题10:二进制中1的个数
- kubernetes-v1.20.4 二进制部署-Metrics-Server服务
- kubernetes-v1.20.4 二进制部署-Calico网络组件、Dashboard和CoreDNS
- kubernetes-v1.20.4 二进制部署-rancher-v2.5.1、harbor
- Centos7 k8s v1.5.2二进制部署安装-flannel之NAT规则优化
- LeetCode-762. 二进制表示中质数个计算置位【二进制,质数,判断质数优化】
- Leetcode0762. 二进制表示中质数个计算置位(simple)
- 2380. 二进制字符串重新安排顺序需要的时间
- 1545. 找出第 N 个二进制字符串中的第 K 位-递归法
- 1582. 二进制矩阵中的特殊位置-时间空间双重优化算法
- Java 实现十进制数转换为二进制
- Redis的那些事儿:关系型和非关系型数据库,非关系型数据库的类型,redis数据类型、编码格式、高性能、可以做什么、分布式锁失效的原因,string为采用sds数据类型,为什么是二进制安全的,
- 06Linux系统中docker安装 docker install in centos7.源码安装 二进制安装编译export无网络不联网安装conda
- Kubernetes二进制部署高可用集群
- a37.ansible 生产实战案例 -- 基于二进制包安装kubernetes v1.23 -- 集群部署(一)