摘要
Title: 1047. 糖果
Tag: 01背包
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

1047. 糖果

• 题意

  由于在维护世界和平的事务中做出巨大贡献，Dzx被赠予糖果公司2010年5月23日当天无限量糖果免费优惠券。
  在这一天，Dzx可以从糖果公司的 N 件产品中任意选择若干件带回家享用。
  糖果公司的 N 件产品每件都包含数量不同的糖果。
  Dzx希望他选择的产品包含的糖果总数是 K 的整数倍，这样他才能平均地将糖果分给帮助他维护世界和平的伙伴们。
  当然，在满足这一条件的基础上，糖果总数越多越好。
  Dzx最多能带走多少糖果呢？
  注意：Dzx只能将糖果公司的产品整件带走。

• 思路

  注意这里是不用优化为一维的，一般的背包问题基本不用优化
  

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-04-02 20:46:56
  FilePath: \ACM\Acwing\1047.py
  LastEditTime: 2022-04-02 20:46:57
  '''
  N = 110
  INF = int(1e18)
  f = [[-INF] * N for _ in range(N)]
  n, k = map(int, input().split())
  w = [0]
  for i in range(n):
      w.append(int(input()))
  
  f[0][0] = 0 #只有当 选前i个物品，价值模k等于0，是合法的，其他的像f[0][1]是不合法的
  for i in range(1, n + 1):
      for j in range(k):
          f[i][j] = max(f[i - 1][j], f[i - 1][(j - w[i]) % k] + w[i])
  
  print(f[n][0])