华科不平凡

题解

/ 注册

全部文章 / 题解（共3篇）

购物单（背包问题）来自专栏

出题者觉得0/1背包太套路了，因此给我们使了点小绊子，但是问题不大。设主件个数为n，奖金数量为M，每个主件对应的价格为v，每个主件对应的重要程度为w。d[i][j]表示从前i个主件中选取，奖金数量为j的情况下，所获得的最大价格*重要程度累加和。另外注意到一个小细节：每个主件只能有0～2个附件，最多...

背包问题动态规划

2020-08-27

324 15888

最少邮票个数来自专栏

首先，这是一个背包问题。描述转化为“背包”，有N个物品，每个物品的质量为Vi，背包重量为M，求最少取多少个物品才能刚好装满背包，如果无法满足条件，返回0。我们用INT32_MAX表示无法凑齐，设dp[i][j]为邮票为前i张时，刚好凑成j所需要的最小邮票张数，有以下状态公式：当j-v[i-1]...

背包问题动态规划

2020-08-27

1 760

0/1背包问题来自专栏

“求价值最大和”，毋庸置疑，用动态规划。此类题目属于动态规划中的一个特殊类别——“背包问题”。 PS：背包问题可以分为三种—— 0/1背包问题——物品只有选/不选两种状态，求最大价值和子集背包问题——分割等和子集问题完全背包问题——物品可以无限选，求可以组合成目标值的选法设当前个数为i，当...

背包问题动态规划

2020-08-26

2 833