文章

16

粉丝

133

获赞

47

访问

37.6k

头像
数字游戏 - 中南大学 题解:动态规划
P1934 中南大学2023年机试题
发布于2025年5月5日 11:23
阅读数 69

这道题目要求我们找出使用给定数字(可以重复使用)凑出目标数m所需的最少数字数量。如果无法凑出目标数,则返回-1。这是一个典型的动态规划问题,类似于背包问题。

方法思路

  1. 问题分析:我们需要用最少的数字组合来达到目标数m。每个数字可以重复使用,类似于完全背包问题,但这里我们需要最小化使用的数字数量而不是最大化价值。

  2. 动态规划:使用一个数组dp,其中dp[i]表示凑出数字i所需的最少数字数量。初始化时,dp[0] = 0(凑出0需要0个数字),其他位置的初始值设为一个大数(表示不可达)。

  3. 状态转移:对于每一个数字x,遍历从xm的所有可能值i,更新dp[i]min(dp[i], dp[i - x] + 1)

  4. 结果检查:最后检查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++) {
         ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发