0-1背包问题(the knapsack problem)

2018-06-17 22:10:40来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

---恢复内容开始---

  关键原理:动态规划。

    tab[i][j] = max(tab[i-1][j-weight[i]]+value[i],tab[i-1][j]) ({i,j|0<i<=n,0<=j<=total})

    i表示放第i个物品,j表示背包所容纳的重量,那么tab[i-1][j-weight[i]]+value[i]表示放入第i物品。

流程:

 

状态转移方程:

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:P2894 [USACO08FEB]酒店Hotel

下一篇:HDU 6040---Hints of sd0061(STL)