背包问题的外围公式
把每个背包问题的外围代码放在一块,更好的辨别不同问题的代码实现。当然,在实现代码之前,要先理解每个背包问题解决问题的思路。
物品的分量数组是 weight (int[])
,价值数组是 value (int[])
,背包容量是 bagWeight
1. 0-1 背包
从大到小遍历,为了保障每个物品仅被增加一次
1.1 应用二维数组存储
递推公式
dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i])
(dp[i][j]
:放入物品和不放入物品,哪个值大 )
dp
大小
int[weight.size()][bagWeight+1]
([物品个数][背包容量 +1]
)
代码
// 先遍历物品,再遍历背包
for(int i = 0; i < weight.size(); i++) {for(int j = bagWeight; j >= 0; j--) {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])
}
}
1.2 应用一维数组存储
递推公式
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
(dp[j]
:放入物品和不放入物品,哪个值大 )
dp
大小
int[bagWeight+1]
([背包容量 +1]
)
代码
// 先遍历物品,再遍历背包
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]);
}
}
2. 齐全背包
齐全背包的物品是能够增加屡次的,所以要从小到大去遍历
2.1 组合
递推公式
dp[j] = max(dp[j], dp[j-nums[i]])
(dp[j]
:由 dp[1], dp[2], ... dp[j-1]
而来 )
递推公式依据理论状况有所变动,通过找寻 dp[j]
是怎么通过其余的 dp
值推导而确定公式
dp
大小
int[bagWeight+1]
([背包容量 +1]
)
代码
// 先遍历物品,再遍历背包
for (int i = 0; i < weight.size(); i++) {for(int j = weight[i]; j < bagWeight ; j++) {dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
}
}
2.2 排列
递推公式
dp[j] = dp[j-nums[i]]
(dp[j]
:由 dp[1], dp[2] ... dp[j-1]
而来 )
递推公式依据理论状况有所变动,通过找寻 dp[j]
是怎么通过其余的 dp
值推导而确定公式
dp
大小
int[bagWeight+1]
([背包容量 +1]
)
代码
// 先遍历背包,再遍历物品
for(int j = 0; j <= bagWeight; j++) {for(int i = 0; i < weight.size(); i++) {if (j >= wieght[i]) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}