总结6..

背包问题的解决过程

在解决问题之前，为描述方便，首先定义一些变量：Vi表示第 i 个物品的价值，Wi表示第 i 个物品的体积，定义V(i,j)：当前背包容量 j，前 i 个物品最佳组合对应的价值，同时背包问题抽象化（X1，X2，…，Xn，其中 Xi 取0或1，表示第 i 个物品选或不选）。

1、建立模型，即求max(V1X1+V2X2+…+VnXn)；

2、寻找约束条件，W1X1+W2X2+…+WnXn<capacity；

3、寻找递推关系式，面对当前商品有两种可能性：

包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即V(i,j)=V(i-1,j)；

还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝。

其中V(i-1,j)表示不装，V(i-1,j-w(i))+v(i) 表示装了第i个商品，背包容量减少w(i)，但价值增加了v(i)；

由此可以得出递推关系式：

j<w(i) V(i,j)=V(i-1,j)

j>=w(i) V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝

 #include <stdio.h>

int main() {

    // 定义数组a用于存储每个节点的权值，数组b作为邻接矩阵存储节点间的连接关系

    // dp数组用于存储从每个节点出发能得到的最大权值和，d数组用于记录路径

    int a[30], b[30][30] = {0}, n, dp[30] = {0}, d[30] = {0};

    // 读取节点的数量n

    scanf("%d", &n);

    // 读取每个节点的权值，存储到数组a中，这里从a[1]到a[n]存储有效数据

    for (int i = 1; i <= n; i++)

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

 

    // 读取邻接矩阵b的上三角部分，表示节点之间的连接关系

    // b[i][j]为1表示节点i到节点j有一条边

    for (int i = 1; i < n; i++) {

        for (int j = i + 1; j <= n; j++) {

            scanf("%d", &b[i][j]);

        }

    }

 

    // 初始化dp[n]为节点n的权值，因为从节点n出发没有后续节点，所以它的最大权值和就是自身权值

    dp[n] = a[n];

    // 记录当前最大权值和对应的节点编号，初始化为n

    int maxi = n;

 

    // 从倒数第二个节点开始向前遍历，计算从每个节点出发的最大权值和

    for (int i = n - 1; i >= 1; i--) {

        // 初始化dp[i]为节点i的权值

        dp[i] = a[i];

        // 初始化d[i]为0，表示当前还没有找到后续能使权值和更大的节点

        d[i] = 0;

 

        // 遍历节点i之后的所有节点j，寻找从节点i到节点j的路径

        for (int j = i + 1; j <= n; j++) {

            // 如果节点i到节点j有边，并且通过节点j能使从节点i出发的权值和更大

            if (b[i][j] == 1 && dp[j] + a[i] > dp[i]) {

                // 更新从节点i出发的最大权值和

                dp[i] = dp[j] + a[i];

                // 记录使权值和最大的后续节点j

                d[i] = j;

            }

        }

 

        // 如果当前节点i的最大权值和大于之前记录的最大权值和

        if (dp[i] > dp[maxi])

            // 更新最大权值和对应的节点编号为i

            maxi = i;

    }

 

    // 从最大权值和对应的节点maxi开始，按照记录的路径输出路径上的节点

    int t = maxi;

    while (t > 0) {

        printf("%d ", t);

        t = d[t];

    }

    printf("\n");

    // 输出从最大权值和对应的节点出发能得到的最大权值和

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

    return 0;

}

 #include <stdio.h>

 

// 定义一个函数max，用于返回两个整数中的较大值

int max(int a, int b) {

    return a > b? a : b;

}

 

int main() {

    // t表示背包的容量，m表示物品的数量

    // w数组用于存储每个物品的重量，v数组用于存储每个物品的价值

    // dp数组是动态规划的核心数组，dp[i][j]表示考虑前i个物品，背包容量为j时能获得的最大价值

    int t, m, w[103], v[103], dp[103][1003];

 

    // 读取背包的容量t和物品的数量m

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

 

    // 依次读取每个物品的重量和价值，并存储到w数组和v数组中

    for (int i = 1; i <= m; i++) {

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

    }

 

    // 动态规划核心部分，通过两层循环填充dp数组

    // 外层循环遍历每个物品，从第1个物品到第m个物品

    for (int i = 1; i <= m; i++) {

        // 内层循环从背包容量t开始递减到0，用于计算在不同背包容量下的最大价值

        for (int j = t; j >= 0; j--) {

            // 如果当前背包容量j大于等于当前物品i的重量w[i]，说明可以放入该物品

            if (j >= w[i]) {

                // 此时有两种选择：放入物品i，价值为dp[i - 1][j - w[i]] + v[i]；不放入物品i，价值为dp[i - 1][j]

                // 取两者中的较大值作为dp[i][j]的值

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

            } else {

                // 如果当前背包容量j小于当前物品i的重量w[i]，则无法放入该物品

                // 此时dp[i][j]的值等于不考虑当前物品i时，背包容量为j的最大价值，即dp[i - 1][j]

                dp[i][j] = dp[i - 1][j];

            }

        }

    }

 

    // 输出考虑所有m个物品，背包容量为t时能获得的最大价值

    printf("%d", dp[m][t]);

 

    return 0;

}