0-1背包详细解释加代码注释

问题:

有n种物品,每种只有一个。第i种物品的体积为Vi,重量为Wi。选一些物品装到一个容量为C的背包,使得背包内物品在总体积不超过C的前提下重量尽量大。

1 <= n <= 100

1 <= Vi <= C <= 10000

1 <= Wi <= 1000000

方法:

  • 题目为求把第1,2,3,…,n个物品装到容量为C的背包中的最大重量,那么设d(i,j)表示把第i,i+1,i+2,…,n个物品装到容量为j的背包中的最大重量。答案为d(1,C)。
  • 那么在处理第i个物品时有两个选择,放入背包和不放入背包
    • 如果第i个物品不放入背包,那么d(i, j) = d(i + 1, j),表示这和把第i+1,i+2,…,n个物品装到容量为j的背包中的最大重量一样
    • 如果第i个物品放入了背包,那么要从i+1层来获得数据的话,肯定是从第i+1,i+2,…,n个物品装到容量为j-V[i]获得。因为第i个物品放入了背包,下一层时容量变小了
      • d(i+1, j-V[i])
      • 因为d(i, j)表示的含义是背包中的最大重量,因为第i个物品放入了背包,所以重量有增加,最后的表达式为d(i, j) = d(i + 1, j - V[i]) + W[i]
    • 这两种情况都有可能,那么就取最大值吧
  • d(i, j) = max{d(i + 1, j), d(i + 1, j - V[i]) + W[i]}
  • 因为第i层数据从第i+1层来,所以对i的循环要逆序,从大到小
  • 第n层的数据d(n, j)表示把第n个物品装到容量为j的背包中的最大重量,没有第n+1层了,所以直接判断此边界
    • 如果能放进且放进去的话,d(n, j) = V[n]
    • 如果不能放进或不想放进的话,d(n, j) = 0

代码

for (int j = 0; j <= C; j++){
    // 处理第n层的边界情况
    if (j >= V[n]){
        // 如果能放进去那肯定选择放进去
        d[n][j] = W[n];
    }
    else{
        // 不能放进去就为0
        d[n][j] = 0;
    }
}
for (int i = n - 1; i >= 1; i--){
    // n要逆序,从第n-1层开始
    for (int j = 0; j <= C; j++){
        // j的循环次序无所谓
        d[i][j] = d[i + 1][j];  // 先假设不放进去
        if (j >= V[i]){
            // 如果能放进去且放进去的话
            d[i][j] = max(d[i][j], d[i + 1][j - V[i]] + W[i]);
        }
    }
}

如果要合并边界和一般情况,可以加一个n + 1层,使其全部初始化为0

memset(d, 0, sizeof(d));
for (int i = n; i >= 1; i--){
    // 从第n层开始
    for (int j = 0; j <= C; j++){
        d[i][j] = d[i + 1][j];  // 先假设不放进去
        if (j >= V[i]){
            d[i][j] = max(d[i][j], d[i + 1][j - V[i]] + W[i]);
        }
    }
}

发表评论