C语言实现完全背包问题

完全背包问题指的是有n件物品和一个容量为V的背包，第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

C语言实现：

#include <stdio.h>
#define MAX(a,b) ((a)>(b)?(a):(b))

int main()
{
    int n, V;
    scanf("%d %d", &n, &V);
    int w[n], v[n];
    for(int i=0; i<n; i++) 
        scanf("%d %d", &w[i], &v[i]);
    int dp[V+1]; // dp[i]表示容量为i的背包可获得的最大价值
    for(int i=0; i<=V; i++) dp[i] = 0; // 初始化
    for(int i=0; i<n; i++)
        for(int j=w[i]; j<=V; j++) 
            dp[j] = MAX(dp[j], dp[j-w[i]]+v[i]); // 状态转移方程
    printf("%d\n", dp[V]); // 输出最大价值
    return 0;
}

在上述代码中，首先输入n和V，以及每个物品的重量和价值。然后，定义一个大小为V+1的数组dp，用于记录容量为i的背包可获得的最大价值。接着，进行初始化，即令所有dp[i]的值为0。最后，使用双重循环进行状态转移，更新dp数组的值，直到得到容量为V的背包可获得的最大价值。最后，输出最大价值即可。

时间复杂度为O(nV)，其中n为物品的数量，V为背包的容量。空间复杂度为O(V)，即需要一个大小为V+1的数组dp。