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分
8 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复