[NOIP2001]装箱问题（c语言版）

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;  

}