Celery's Blog

0%

LeetCode-Day52

发表于 Valine：

继续背包…

二维费用背包

问题

二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第ii件物品所需的两种代价分别为w[i]w[i]和g[i]g[i]。两种代价可付出的最大值（两种背包容量）分别为VV和TT。物品的价值为v[i]v[i]。

算法

费用增加了一维，只需状态也加一维即可。设f[i][j][k]f[i][j][k]f[i][j][k]表示前i件物品付出两种代价分别为j和k时可获得的最大价值。状态转移方程就是：f[i][j][k]=max(f[i−1][j][k],f[i−1][j−w[i]][k−g[i]]+v[i])f[i][j][k]=max({f[i-1][j][k],f[i-1][j-w[i]][k-g[i]]+v[i]})f[i][j][k]=max(f[i−1][j][k],f[i−1][j−w[i]][k−g[i]]+v[i])
如前述方法，可以只使用二维的数组：当每件物品只可以取一次时变量jj和kk采用逆序的循环，当物品有如完全背包问题时采用顺序的循环。当物品有如多重背包问题时拆分物品。代码：

1
2
3
4
for (int i = 1; i <= n; i++)
    for (int j = V; j >= w[i]; j--)
        for (int k = T; k >= g[i]; k--)
            f[j][k] = max(f[j][k], f[j - w[i]][k - g[i]] + v[i]);

物品总个数的限制

有时，“二维费用“的条件是以这样一种隐含的方式给出的：最多只能取MM件物品。这事实上相当于每件物品多了一种“件数”的费用，每个物品的件数费用均为1，可以付出的最大的件数费用为M。换句话说，设f[i][j]f[i][j]表示付出费用ii，最多选jj件时可得到的最大价值，则根据物品的类型(01，完全，多重)用不同的方法循环更新，最后在f[0...V][0...M]f[0...V][0...M]范围内寻找答案。

HDU 2159 FATE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
int w[MAXN], v[MAXN];
int dp[MAXN][MAXN];
int n, m, k, s;

void solve() {
    int res = INT_MAX;
    memset(dp, 0, sizeof(dp));
    for(int i = 0; i < k; i++) {
        for(int j = 1; j <= s; j++) {
            for(int p = w[i]; p <= m; p++) {
                dp[j][p] = max(dp[j][p], dp[j - 1][p - w[i]] + v[i]);
            }
        }
    }
    for(int i = 0; i <= s; i++) {
        for(int j = 0; j <= m; j++) {
            if(dp[i][j] >= n) {
                res = min(res, j);
            }
        }
    }
    printf("%d\n", res == INT_MAX ? -1 : m - res);
}

int main() {
    while(scanf("%d%d%d%d", &n, &m, &k, &s) != EOF) {
        for(int i = 0; i < k; i++) {
            scanf("%d%d", &v[i], &w[i]);
        }
        solve();
    }
}

分组背包的问题

有NN件物品和一个容量为VV的背包。第ii件物品的费用是w[i]w[i]，价值是v[i]v[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

f[k][j]表示前k组物品花费费用j能取得的最大权值。

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

1
2
3
4
for (所有的组k)
    for (int j = V; j >= 0; j--)
        for (所有属于组k的i)
            f[j] = max{f[j], f[j - w[i]] + v[i]}

例题：

HDU 1712 ACboy needs your help

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
int dp[MAXN];
int A[MAXN][MAXN];
int n, m;

void solve() {
    memset(dp, 0, sizeof(dp));
    for(int k = 0; k < n; k++) {
        for(int j = m; j >= 0; j--) {
            for(int i = 0; i < j; i++) {
                dp[j] = max(dp[j], dp[j - (i + 1)] + A[k][i]);
            }
        }
    }
    printf("%d\n", dp[m]);
}

int main() {
    while(scanf("%d%d", &n, &m) && (m || n)) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                scanf("%d", &A[i][j]);
            }
        }
        solve();
    }

}