1.数组索引的使用:

在C语言中,数组索引是从0开始的。但是,你的代码中对v和dp数组的访问是从1开始的(v[i]和dp[j]在循环中从1开始遍历)。这可能导致未定义行为(访问数组边界之外的内存),因为v[0]和dp[0]等位置从未被初始化或赋值。

动态规划数组dp的初始值:

在处理背包问题时,通常需要将dp数组初始化为0或根据问题的具体需求进行初始化。在你的代码中,dp数组未被显式初始化,其初始值是不确定的(取决于内存中的状态)。这可能导致不正确的结果。

背包问题的目标理解:

2.你的代码中使用了n - dp[n]来输出结果,这看起来像是试图求出一个“剩余”的值,但这通常不是背包问题的标准输出。在标准的0-1背包问题中,我们关注的是能够放入背包中的物品的最大价值或重量,而不是剩余的部分。如果你的目的是计算剩余容量或其他,这个输出方式可能是正确的,但需要确保这与你的问题描述相匹配。

3.对dp数组的更新逻辑:

你的更新逻辑dp[j] = max(dp[j], dp[j - v[i]] + v[i]);是正确的,但前提是j >= v[i],这是由背包问题的性质决定的。你已经通过if (v[i] <= j)检查了这个条件,这是好的。

4.对n和m的理解:

n通常被理解为背包的容量或限制,而m是物品的数量。确保你的输入和代码逻辑与这一点保持一致。

参考代码如下:

#include<stdio.h>  

int v[31];  

int dp[20001];

int max(int a, int b) {  

    if (a > b) return a;  

    else return b;  

}  

int main() {  

    int n, m;  

    scanf("%d%d", &n, &m);  

    for (int i = 1; i <= m; i++) {  

        scanf("%d", &v[i]);  

    }  

   

    for (int j = 0; j <= n; j++) {  

        dp[j] = 0;  

    }  

    for (int i = 1; i <= m; i++) {  

        for (int j = n; j >= v[i]; j--) { // 确保j >= v[i]  

            dp[j] = max(dp[j], dp[j - v[i]] + v[i]);  

        }  

    }    

    printf("%d\n", n - dp[n]);  

    return 0;  

}


点赞(0)
 

0.0分

8 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 5 条评论

041叶飞 4月前 回复TA
姬  霓  钛  镁
041叶飞 4月前 回复TA
罗小姨好美好美
020张叶军 4月前 回复TA
@022罗晓熠 @dotcpp0785444 我嘞个ikun
021文彦钦 4月前 回复TA
@022罗晓熠 我勒个小鸡
022罗晓熠 4月前 回复TA
我勒个逗