1047. 糖果(01背包)
01 背包 糖果
2023-09-14 09:01:26 时间
Question
由于在维护世界和平的事务中做出巨大贡献,Dzx被赠予糖果公司2010年5月23日当天无限量糖果免费优惠券。
在这一天,Dzx可以从糖果公司的 N 件产品中任意选择若干件带回家享用。
糖果公司的 N 件产品每件都包含数量不同的糖果。
Dzx希望他选择的产品包含的糖果总数是 K 的整数倍,这样他才能平均地将糖果分给帮助他维护世界和平的伙伴们。
当然,在满足这一条件的基础上,糖果总数越多越好。
Dzx最多能带走多少糖果呢?
注意:Dzx只能将糖果公司的产品整件带走。
输入格式
第一行包含两个整数 N 和 K。
以下 N 行每行 1 个整数,表示糖果公司该件产品中包含的糖果数目,不超过 1000000。
输出格式
符合要求的最多能达到的糖果总数,如果不能达到 K 的倍数这一要求,输出 0。
数据范围
1≤N≤100,
1≤K≤100,
输入样例:
5 7
1
2
3
4
5
输出样例:
14
样例解释
Dzx的选择是2+3+4+5=14,这样糖果总数是7的倍数,并且是总数最多的选择。
Ideas
01背包(有限制的选择性问题)
Code
# 01背包问题 O(N^2)
'''
调DP bug的时候可以从运行结果入手 走几个例子
'''
n,m = list(map(int,input().strip().split()))
N = 110
f = [[-float('inf') for i in range(N)] for j in range(N)] # 代表前i个物品 和是k的倍数的选法的最大值
w = [0 for i in range(N)]
f[0][0] = 0
for i in range(1,n+1):
w[i] = int(input())
for j in range(m+1):
f[i][j] = max(f[i-1][j],f[i-1][(j-w[i])%m]+w[i])
print(f[n][0])
相关文章
- I NEED A OFFER! 1203 (01背包变形+数学)
- Spring基础-01
- 【并发技术01】传统线程技术中创建线程的两种方式
- hdu3339 In Action(Dijkstra+01背包)
- 数据结构Java实现01----算法概述
- Java实现 蓝桥杯 算法提高 01背包
- Python基于回溯法解决01背包问题实例
- 01. Update your emulator with newest services apk
- Python基于回溯法解决01背包问题实例
- 01背包问题(DP)
- 【BSP视频教程】BSP视频教程第25期:CAN/CANFD/CANopen专题,CAN知识点干货分享, 收发执行过程和错误帧处理(2023-01-03)
- LintCode 125 · 背包问题(二)---01背包问题
- IBASE category 设置为01的情况下 IBASE自动创建情况
- 算法设计 - 01背包问题
- 003-结构型-01-适配器模式(Adapter)
- 01 openEuler操作系统介绍
- hdu 2546 饭卡 01背包
- 初识Archaius的简单使用及高级使用-01
- 【jQuery】jQuery概述及jQuery的原理_01
- HTML5 ——《第二章—01》HTML5页面元素
- Git的安装、配置、使用01【Git Bash Here命令行操作】
- 01背包问题
- 278. 数字组合(01背包,恰好)
- 8. 二维费用的背包问题(01背包)
- 2. 01背包问题(背包模型)
- Latex数学公式编辑常用命令技巧集锦(2022-01-04更新)
- 动态规划02---你的背包怎么背也背不烂~~~专治各种01背包问题