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 算法基础课 动态规划的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!