正在查看旧版本。 查看 当前版本.

与当前比较 查看页面历史记录

« 前一个 版本 3 下一个 »

01背包

有N件物品和一个容量为V的背包，第i件物品的费用是c[i]，价值是w[i]，求将哪些物品装入背包可使总费用不超过背包的容量，且价值之和最大。

重点：每件物品仅有一件，可以取或不取。

解题思路：

定义F[i][v]表示将第i件物品放入一个容量恰好为v的背包的价值，则其状态转移方程如下：

F[i][v] = max{F[i-1][v], F[i-1][v-c[i]] + w[i]}

上面的这个方程的含义如下：

  1. 将第i件物品放入容量为v的背包的最大价值，只需要考虑第i件物品是否放入背包，有放和不放两种情况。
  2. 如果不放第i件物品，那么总价值就是前i-1件物品放入容量为v的背包的价值，也就是F[i-1][v]。
  3. 如果放入第i件物品，那么就价值就是第i件物品的价值w[i]，加上前i-1件物品放入容量为v-c[i]的背包的价值F[i-1][v-c[i]]。
  4. 以上两者取最大值，即为第i件物品放入容量为v的背包的最大价值。

代码实现如下：

#define MAXN 1005

int n; // 物品数
int v; // 背包容量

int c[MAXN]; // 物品费用 
int w[MAXN]; // 物品价值
int f[MAXN][MAXN]; // f[i][j]，j体积下前i个物品的最大价值

int knapsack01() {
    cin >> n >> v;
    for(int i = 1; i <= n; i++) { // 下标从1开始
        cin >> c[i] >> w[i];
    }

    // 注意这里隐含设置了取0件物品和背包容量为0时f数组对应的值全为0的情况
    // for(int i = 0; i <= v; i++) f[0][i] = 0;
    // for(int i = 0; i <= n; i++) f[i][0] = 0;

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= v; j++) {
            if(j < c[i]) {
                // 当前背包容量j装不下第i个物品，则价值等于前i-1个物品
                f[i][j] = f[i-1][j];
            } else {
                // 能装，按方程进行决策
                // 注意，当到j恰好能装下全部的前i件物品时，
                // 后续的j可直接设置成f[i][j-1]，因为后续的j表示背包容量已经有冗余了
                f[i][j] = max(f[i-1][j], f[i-1][j - c[i]] + w[i]);
            }
        }
    }

    return f[n][v];
}











  • 无标签