【挑战程序设计竞赛】 背包问题

发表于

描述
n个物品，有不同的重量weight[n],有不同的价值price[n]
你有一个能承载重量为A的背包，问能带走的最大价值是多少。

暴力搜索
每一个物品都有可能带走或者不带走，枚举出所有情况，此时可以采用深度优先搜索。

notes:price+0代表最后一个节点的价值，dfs+price中price表示保存当前价值，再看看加上后续的点会不会更优解，可以用二叉树理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
int dfs(int i,int j) {
    if (i == n) {
        return 0;
    }
    if (j < weight[i]) {
        //can not take the item
        return dfs(i+1,j);
    }
    else {
        //can take the item or not take it
        return max(dfs(i+1,j), dfs(i + 1, j - weight[i]) + price[i]);
    }
}

记忆搜索1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int dp1[100][100];

int dfs2(int i, int j) {
    int res = 0;
    if (dp1[i][j] != 0) {
        return dp1[i][j];
    }

    if (i == n) {
        res =  0;
    }
    else if (j < weight[i]) {
        //can not take the item
        res =  dfs2(i + 1, j);
    }
    else {
        //can take the item or not take it
        res =  max(dfs2(i + 1, j), dfs2(i + 1, j - weight[i]) + price[i]);
    }
    return dp1[i][j] = res;
}

记忆搜索2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int solve() {
    vector<vector<int>> dp2(n+1,vector<int>(A+1,0));
    for (int i = n-1; i >= 0; i--) {
        for (int j = 0; j <= A; j++) {
            if (j < weight[i]) {
                dp2[i][j] = dp2[i + 1][j];
            }
            else {
                dp2[i][j] = max(dp2[i + 1][j], dp2[i + 1][j - weight[i]] + price[i]);
            }
        }
    }
    return dp2[0][A];
}

递推法
dp[i+1][j]为前i个物品负重为j的最大价值。
当i=0时，为dp[0+1][j]代表的含义为一个物品重量为j的最大价值。
dp[2][10] = max{dp[1][10],dp[1][10-weight[1]]+price[1]};
物品和价值都是从0开始的，也就是说weight[1]实际上代表的就是第二个的重量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int solve2() {
    vector<vector<int>>dp3(n + 1, vector<int>(A + 1, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= A; j++) {
            if (j < weight[i]) {
                dp3[i + 1][j] = dp3[i][j];
            }
            else {
                dp3[i + 1][j] = max(dp3[i][j], dp3[i][j - weight[i]] + price[i]);
            }
        }
    }
    return dp3[n][A];
}

转移状态
一个物品的选用和不选用两种状态，也就是会影响前i+1个物品最大负重量为j(不选中)和j-weight[i+1](选中)。

1
2
3
4
5
6
7
8
9
10
11
12
int solve3() {
    vector<vector<int>> dp4(n + 1, vector<int>(A + 1, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= A; j++) {
            dp4[i + 1][j] = max(dp4[i + 1][j], dp4[i][j]);
            if (j + weight[i] <= A) {
                dp4[i + 1][j + weight[i]] = max(dp4[i + 1][j + weight[i]], dp4[i][j] + price[i]);
            }
        }
    }
    return dp4[n][A];
}