背包问题算法

MoyiTech
2023-11-24 / 0 评论 / 58 阅读 / 正在检测是否收录...

01背包问题

01背包是一种动态规划问题。动态规划的核心就是状态转移方程

有一个容量为V的背包,还有n个物体。现在忽略物体实际几何形状,我们认为只要背包的剩余容量大于等于物体体积,那就可以装进背包里。每个物体都有两个属性,即体积w和价值v。 问:如何向背包装物体才能使背包中物体的总价值最大?

二维数组解法

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

i:选用前i种物品

j:背包容量为j

dp[i][j] 表示从下标为[0,i]的物品里任意取,放进容量为j的背包,价值总和最大是多少

for (int j = 0 ; j < weight[0]; j++) {  // 如果把dp数组预先初始化为0了,这一步就可以省略。
    dp[0][j] = 0;
}
// 正序遍历
for (int j = weight[0]; j <= bagWeight; j++) {
    dp[0][j] = value[0];
}

有两个遍历维度:1. 物品背包容量。 2. 所以要确定遍历顺序。

两者都可以,先遍历物品好理解。

先遍历物品,然后遍历背包重量:

// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j]; // 如果不能放下物品i
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}

先遍历背包,再遍历物品:

// weight数组的大小就是物品个数
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}

为什么两种顺序都可以?要理解递归的本质和递推的方向。那么先遍历物品,再遍历背包的过程和先遍历背包,再遍历物品,dp[i][j]所需要的数据就是左上角,根本不影响dp[i][j]公式的推导。

lpcg112l.png

一维dp数组解决01背包问题

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

一维dp数组如何初始化

dp[j]表示:容量为j的背包,所背的物品价值可以最大为dp[j],那么dp[0]就应该是0,因为背包容量为0所背的物品的最大价值就是0。

假设物品价值都是大于0的,所以dp数组初始化的时候,都初始为0就可以了。

一维dp数组遍历顺序

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

lpcg1b0w.png

  • 01背包中二维dp数组的两个for遍历的先后循序是可以颠倒,一维dp数组的两个for循环先后循序一定是先遍历物品,再遍历背包容量。
  • 和二维dp的写法中,遍历背包的顺序是不一样的!一维dp遍历的时候,背包容量是从大到小:倒序遍历是为了保证物品i只被放入一次!

为什么一维dp数组必须倒序遍历:

如图,红线为数据更新来源,蓝线数据更新顺序:当前状态源于左上角同背包容量方向

  • 如果先遍历物品再遍历背包且正序遍历,就会使一些同背包容量方向的数据被覆盖掉。
  • 如果先遍历背包再遍历物品,

完全背包问题

完全背包依然是一个动态规划问题

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品都有无限个(也就是可以放入背包多次),求解将哪些物品装入背包里物品价值总和最大。

完全背包和01背包问题唯一不同的地方就是,每种物品有无限件

01背包和完全背包唯一不同就是体现在遍历顺序上,所以针对遍历顺序进行分析。

// 先遍历物品,再遍历背包
int[] dp = new int[bagWeight + 1];
for (int i = 0; i < weight.length; i++){
    for (int j = 1; j <= bagWeight; j++){
        if (j - weight[i] >= 0){
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
}

为什么遍历物品在外层循环,遍历背包容量在内层循环?

01背包中二维dp数组的两个for遍历的先后循序是可以颠倒,一维dp数组的两个for循环先后循序一定是先遍历物品,再遍历背包容量。

完全背包中,对于一维dp数组来说,其实两个for循环嵌套顺序无所谓:因为物品可以重复装。也就是说dp[j]是根据下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以。完全背包中,两个for循环的先后循序,都不影响计算dp[j]所需要的值。

为什么是正序遍历而不是倒序遍历了?

因为在完全背包中,由于物品可以重复装填,那么就需要相同物品在不同背包容量时重复利用前面的数据。

lpcg1l2l.png

先遍历背包再遍历物品:

// 先遍历背包,再遍历物品
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

lpcg1s8x.png

先遍历物品,再遍历背包:

// 先遍历物品,再遍历背包
int[] dp = new int[bagWeight + 1];
for (int i = 0; i < weight.length; i++){
    for (int j = 1; j <= bagWeight; j++){
        if (j - weight[i] >= 0){
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
}

连续背包问题

连续背包问题是指有一个容量为V的背包和n个物品,每个物品有一个体积v [i]和一个价值w [i],现在要将这些物品放入背包中,使得背包中物品的总价值最大。 与0/1背包问题不同的是,每个物品可以被放入多次,即是连续的。

解题思路:单位价值优先使用贪心算法

① 按价值密度(w/v)进行非递增排序

② 按照排序先后,往里装。单个物品装完时换下一个,直到背包填满为止

2

评论 (0)

取消