C语言动态规划多种背包问题分析讲解

背包问题介绍

背包问题是动态规划中比较常见的问题之一，特别是在算法竞赛中。

一般来说，背包问题可分为两大类：01背包和完全背包。01背包是每个物品只能用一次，而完全背包则是每个物品可以无限制使用。

这里将介绍多种背包问题的分析和具体实现。

01背包问题

问题描述

有一个容量为V的背包和N个物品，每个物品的体积为v[i]，价值为w[i]，求在装满背包的前提下，最大化能够获得的总价值。

分析与实现

01背包问题采用二维数组dp[i][j]记录放置前i个物品，总体积不超过j时的最大价值。

具体地，依次枚举物品i和容量j（即i和j的范围分别为[1, N] 和[1, V] ），讨论第i个物品是否放入背包中：

1. 若第i个物品的体积大于j，则不放入，此时dp[i][j]的值应该和dp[i-1][j]相同；
2. 若第i个物品的体积小于等于j，则可以将其放入背包中，此时dp[i][j]应该等于dp[i-1][j-v[i]] + w[i]；
3. 比较第1步和第2步中两种情况所对应的dp值，选择其中较大的值即可。

下面是C语言的实现代码：

#include <stdio.h>
#include <string.h>

#define maxn 1005

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int N, V;
    int v[maxn], w[maxn];
    int dp[maxn][maxn];

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

    for (int i = 1; i <= N; i++)
        scanf("%d%d", &v[i], &w[i]);

    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= V; j++) {
            if (j < v[i])
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
        }
    }

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

    return 0;
}

完全背包问题

问题描述

有一个容量为V的背包和N个物品，每个物品的体积为v[i]，价值为w[i]，每种物品都有无限个。在装满背包的前提下，最大化能够获得的总价值。

分析与实现

完全背包问题的dp数组和01背包问题一样是二维数组，但转移方程有所不同。

对于每个物品i，依次枚举背包中放入第i个物品的数目（即可能的xi，范围为[0, V/v[i]]），讨论第i个物品所能带来的价值：

1. 若不放入第i个物品，则dp[i][j]的值应直接等于dp[i-1][j]。
2. 若放入x个第i个物品，则dp[i][j]等于dp[i][j-xv[i]] + xw[i]（这里借用前面提到的完全背包思想，将此方程写成这样）。

由此可得dp转移方程为：

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

下面是C语言的实现代码：

#include <stdio.h>
#include <string.h>

#define maxn 1005

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int N, V;
    int v[maxn], w[maxn];
    int dp[maxn][maxn];

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

    for (int i = 1; i <= N; i++)
        scanf("%d%d", &v[i], &w[i]);

    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= N; i++) {
        for (int j = v[i]; j <= V; j++) {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i]);
        }
    }

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

    return 0;
}

示例说明

下面使用两个示例来说明上面介绍的两个问题。

示例1

输入：
4 5
1 2
2 4
3 4
4 5
输出：
9

解释：

这里有4个物品，容量为5，物品分别为1:（1,2），2:（2,4），3:（3,4），4:（4,5）。

使用01背包算法，可以得到最大价值为9，选择物品1和2。

示例2

输入：
4 5
1 2
2 4
3 4
4 5
输出：
10

解释：

这里与示例1相同，但与示例1不同的是，这里使用完全背包算法，最大价值为10，其中选择了物品2和4。