C语言最简单易懂的01背包解法

解题思路:

注意事项:

参考代码:

// DP动态规划  01背包

#include<stdio.h>

int main()

{

    int N, m, v[25], p[25], dp[30000] = { 0 }, i, j, w[25];       //N是背包的最大承载重量。m 是物品的数量。v[i] 是第 i 个物品的重量。p[i] 是第 i 个物品的价值。  dp[j] 是在不超过重量 j 的情况下，可以放入背包的物品的最大价值。

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

    for (i = 0; i < m; i++)

    {

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

        w[i] = v[i] * p[i];

    }

    for (i = 0; i < m; i++)

    {

        for (j = N; j > v[i]; j--)

        {

            if (dp[j] < dp[j - v[i]] + w[i])     //dp[j-v[i]]为背包剩下的空间  w[i]为物品的总价值

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

        }

    }

    printf("%d", dp[N]);

    return 0;

}