题干
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
分析
定义一个二维数组,f[N][N],第一维表示针对于第i个物品选不选的情况,第二维是说限定的体积。在循环继续进行下去的过程中我们通过一步步更新f对于i个物品的状态,就可以得出在针对所有物品的存在状态后就能得到最优解。
代码
1 | #include <iostream> |
代码优化
f当中,我们每一层的优化都是根据上一层的状态更新而来的,所以,我们可以只用一个数组来存储状态,只要保证在下一层在遍历时所用到的当前的数据仍然和上一层的数据相同就可以了。
我们可以从后往前进行遍历,这样就可以保证我们当前正在使用的数据仍然是上一层的数据。
1 | #include <iostream> |
本文作者: jiangyuhao
本文链接: http://example.com/2022/04/07/01%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!
![]()