动态规划解二维多重背包问题

喜欢ヅ旅行 2022-05-29 00:42 188阅读 0赞

### **背包问题** ###

背包问题是一个很经典的算法问题，根据其复杂程度不同又可分为01背包问题、完全背包问题、多重背包问题、二维背包问题等等。本文讲一讲二维多重背包问题的动态规划解法。

#### **01背包问题** ####

有N件物品和一个容量为V的背包。第i件物品的体积是a\[i\]，价值是w\[i\]。求解将哪些物品装入背包可使价值总和最大

#### **完全背包问题** ####

有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是a\[i\]，价格是w\[i\]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大

#### **多重背包问题** ####

有N种物品和一个容量为V的背包。第i种物品最多有n\[i\]件，每件体积是a\[i\]，价值是w\[i\]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大

#### **二维背包问题** ####

有N件物品和一个容量为V，载重为U的背包。第i件物品的体积是a\[i\]，重量是b\[i\]，价值是w\[i\]。求解将哪些物品装入背包可使价值总和最大

### **二维多重背包问题** ###

二维多重背包问题即是多重背包问题和二维背包问题的结合——有N种物品和一个容量为V，载重为U的背包。第i种物品最多有n\[i\]件，每件体积是a\[i\]，重量是b\[i\]，价值是w\[i\]。求解将哪些物品装入背包可使价值总和最大

void backpack(int V, int U, int a[], int b[], int w[], int n[], int N) {
        int i, j, k, l, *x, ***dp;
    
        //初始化
        dp = (int ***) malloc(sizeof(int **) * (N + 1));
        for (i = 0; i <= N; ++i) {
            dp[i] = (int **) malloc(sizeof(int *) * (V + 1));
            for (j = 0; j <= V; ++j) {
                dp[i][j] = (int *) malloc(sizeof(int) * (U + 1));
            }
        }
        for (i = 0; i <= N; ++i) {
            for (j = 0; j <= V; ++j) {
                memset(dp[i][j], 0, sizeof(int) * (U + 1));
            }
        }
        x = (int *) malloc(sizeof(int) * N); //打印方案
        memset(x, 0, sizeof(int) * N);
    
        //求解
        for (i = 1; i <= N; ++i) {
            for (j = a[i - 1]; j <= V; ++j) {
                for (k = b[i - 1]; k <= U; ++k) {
                    dp[i][j][k] = dp[i - 1][j][k];
                    for (l = 1; l <= n[i - 1]; ++l) {
                        if (l * a[i - 1] <= j && l * b[i - 1] <= k) {
                            dp[i][j][k] =
                                    dp[i][j][k]
                                            > (dp[i - 1][j - l * a[i - 1]][k
                                                    - l * b[i - 1]] + l * w[i - 1]) ?
                                            dp[i][j][k] :
                                            (dp[i - 1][j - l * a[i - 1]][k
                                                    - l * b[i - 1]] + l * w[i - 1]);
                        } else {
                            break;
                        }
                    }
                }
            }
        }
    
        //打印
        j = V;
        k = U;
        for (i = N; i > 0; --i) {
            if (dp[i][j][k] > dp[i - 1][j][k]) {
                for (l = 1; l * a[i - 1] <= j && l * b[i - 1] <= k; ++l) {
                    if (dp[i][j][k]
                            == (dp[i - 1][j - l * a[i - 1]][k - l * b[i - 1]]
                                    + l * w[i - 1])) {
                        x[i - 1] = l;
                        j -= l * a[i - 1];
                        k -= l * b[i - 1];
                        break;
                    }
                }
            }
        }
        printf("best value:%d\n", dp[N][V][U]);
        printf("best solution:");
        for (i = 0; i < N; ++i)
            printf("%d ", x[i]);
        printf("\n");
    }

以上是最基础的解法，空间复杂度O(NVU)，时间复杂度O(NVU\*sum(n\[\]))。

附：当只有一维的多重背包问题时，通过单调队列优化，空间复杂度可由O(NV)优化至O(V)，时间复杂度可由O(NV\*sum(n\[\]))优化至O(NV)。  
一维的01背包问题、完全背包问题、多重背包问题解可以见[http://blog.csdn.net/wzy\_1988/article/details/12260343][http_blog.csdn.net_wzy_1988_article_details_12260343]，一维背包打印 [http://www.hawstein.com/posts/dp-knapsack.html][http_www.hawstein.com_posts_dp-knapsack.html]。  
不过上文对多重背包问题未优化，多重背包问题单调队列优化可见[http://alwa.info/2014/05/27/%E5%A4%9A%E9%87%8D%E8%83%8C%E5%8C%85%E5%8D%95%E8%B0%83%E9%98%9F%E5%88%97%E4%BC%98%E5%8C%96/][http_alwa.info_2014_05_27_E5_A4_9A_E9_87_8D_E8_83_8C_E5_8C_85_E5_8D_95_E8_B0_83_E9_98_9F_E5_88_97_E4_BC_98_E5_8C_96] 或 [http://lvat2000.is-programmer.com/posts/185588.html][http_lvat2000.is-programmer.com_posts_185588.html]

[http_blog.csdn.net_wzy_1988_article_details_12260343]: http://blog.csdn.net/wzy_1988/article/details/12260343
[http_www.hawstein.com_posts_dp-knapsack.html]: http://www.hawstein.com/posts/dp-knapsack.html
[http_alwa.info_2014_05_27_E5_A4_9A_E9_87_8D_E8_83_8C_E5_8C_85_E5_8D_95_E8_B0_83_E9_98_9F_E5_88_97_E4_BC_98_E5_8C_96]: http://alwa.info/2014/05/27/%E5%A4%9A%E9%87%8D%E8%83%8C%E5%8C%85%E5%8D%95%E8%B0%83%E9%98%9F%E5%88%97%E4%BC%98%E5%8C%96/
[http_lvat2000.is-programmer.com_posts_185588.html]: http://lvat2000.is-programmer.com/posts/185588.html