Re: [理工] 01大背包问题_列表

楼主: joywilliamjo (joywilliamjoy)   2020-11-04 22:02:15
※ 引述《fmtshk (fmtshk)》之铭言:
: https://i.imgur.com/rtF9VTy.png
: 请问这种题目一定要画出表格吗?
: weight300很大,在表格上通常会怎么列出?
: 感谢各位
我想问一下这题如果做Item对value的表格的话该怎么做
因为题目没有说是0-1knapsack
所以我直接当成一般的knapsack去做
表格画出来这样
https://i.imgur.com/wdf8c1b.jpg
做在w重量限制下,取i个item可以得到的最大value
不知道对不对
问题很多
打扰了
感谢
作者: NTUmaki (西木野真姬)   2020-11-05 02:31:00
不是01的话就能greedy吧 item对value就找固定value 最少要拿多重 backtrace回去看哪一层拿的重量是合理的

Links booklink

Contact Us: admin [ a t ] ucptt.com