C/C++教程

AcWing 算法基础课 动态规划

本文主要是介绍AcWing 算法基础课 动态规划，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1、背包问题

　　(1)01背包

　　每件物品仅用一次　

　　可以做空间优化

　　dp[j]=max(dp[j],dp[j-v[i]]+w[i]);　　　

　　0,1背包状态均是从前一循环的状态转移

　　

　　(2)完全背包

　　每件物品可以用无限次

　　dp[j]=max(dp[j],dp[j-v[i]]+w[i]);

　　

　　完全背包的状态可以从当前循环的状态转移，进行优化

　　

 

 

 

 

 

　　(3)多重背包

　　每件物品有不同的数量限制

　　可以对物品的数量限制进行拆分(1~2^k+c)，从而转化为01背包问题

　　

　　也可以用单调队列进行优化（B站，背包9讲）

　　(4)分组背包

　　组内仅选一件物品  

　　与01背包和完全背包相似，

　　dp时枚举第i组而不是第i个物品，

　　每组中再对组内物品进行枚举。

 

这篇关于AcWing 算法基础课 动态规划的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航