发表于 更新于

背包dp

01背包

顾名思义，每个物品只存在两种状态，用或者不用，且不能重复使用。我们将n个物品储存在一个有限容量的背包中，求其最大价值。那么怎么对dp数组初始化呢？这里我们只需要初始化为0的

1
2
3
4
5
for(i=1;i<=n;i++){
	for(j=m;j>=wei[i];j--){//01背包注意倒序遍历，防止重复利用
        dp[i][j]=max(dp[i-1][j],dp[i-1][j-wei[i]]+val[i]);//核心式子
    }
}

当然，也可以将二维dp数组压缩为一维dp数组，只需要将x维的去掉即可

1
2
3
4
5
for(i=1;i<=n;i++){
	for(j=m;j>=wei[i];j--){
        dp[j]=max(dp[j],dp[j-wei[i]]+wei[i]);
    }
}

完全背包

完全背包和01背包不同的地方在于