这道题目可以看作是一个经典的完全背包问题,其中每种能量块可以视为一种物品,可以无限取用,能量值可以视为物品的“重量”,我们的目标是恰好凑满总能量 m,同时使得使用的能量块数量最少。
定义 dp[i][j] 表示从前 i 种能量块中选取,总能量恰好为 j 时的最少块数。状态转移方程如下:
dp[i][j] = \begin{cases}在实验中,你获得了 n 种不同数值的能量块,每种能量块都有一个正整数能量值。每种能量块都可以无限取用。现在你需要选取若干能量块(同一种可以重复选取),使得它们的总能量恰好等于给定的目标值 m。你的任务是找到所需能量块总数最少的方案,并输出该最少数量。如果没有任何方案能恰好凑出 m,请输出 No solution。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.