文章
16
粉丝
133
获赞
47
访问
37.6k
这道题目要求我们找出使用给定数字(可以重复使用)凑出目标数m所需的最少数字数量。如果无法凑出目标数,则返回-1。这是一个典型的动态规划问题,类似于背包问题。
问题分析:我们需要用最少的数字组合来达到目标数m。每个数字可以重复使用,类似于完全背包问题,但这里我们需要最小化使用的数字数量而不是最大化价值。
动态规划:使用一个数组dp
,其中dp[i]
表示凑出数字i
所需的最少数字数量。初始化时,dp[0] = 0
(凑出0需要0个数字),其他位置的初始值设为一个大数(表示不可达)。
状态转移:对于每一个数字x
,遍历从x
到m
的所有可能值i
,更新dp[i]
为min(dp[i], dp[i - x] + 1)
。
结果检查:最后检查dp[m]
是否仍为大数(表示无法凑出),如果是则返回-1,否则返回dp[m]
。
#include <stdio.h>
#include <limits.h>
#define min(a, b) ((a) < (b) ? (a) : (b))
int main() {
int T;
scanf("%d", &T);
while (T--) {
int n, m;
scanf("%d %d", &n, &m);
int nums[n];
for (int i = 0; i < n; i++) {
scanf("%d", &nums[i]);
}
int dp[m + 1];
dp[0] = 0;
for (int i = 1; i <= m; i++) {
dp[i] = INT_MAX;
}
for (int i = 1; i <= m; i++) {
for (int j = 0; j < n; j++) {
...
登录后发布评论
暂无评论,来抢沙发