对于完全背包状态转移方程的疑问

billryan / algorithm-exercise

Data Structure and Algorithm notes. 数据结构与算法/leetcode/lintcode题解/

https://algorithm.yuanbin.me

3.44k stars 892 forks source link

Closed UltFlash closed 6 years ago

UltFlash commented 6 years ago

详见图，如果可以的话能否给一个即时通讯的联系方式，谢谢~

billryan commented 6 years ago

其实你再仔细看下这道题，是个 01 背包问题，01 背包的我解释不太详细，只是简单提了一下区别，没有把具体过程写出来，最迟这周末更新背包问题的详解

注意看 01 背包问题中的这句话

新的状态转移方程用数学语言来表述即为： $$K(i,\omega) = \max {K(i-1, \omega), K(i-1, \omega - \omega_i) + v_i}$$

你把 K(i, w) 的表达式替换进去就是程序的这段了

UltFlash commented 6 years ago

谢谢回复，理解了一点，看起来的确是一个01背包~感谢分享，希望尽快能看到背包的详解哈哈~

billryan commented 6 years ago

DONE 0f4b75bb4c181274b64bd3e284b42d5b779630fc