力扣背包问题

2024-03-10 17:58:04
开发
23

单个的背包问题大家可能觉得并不是特别困难，但是融入到实际应用之后就很困难了，最困难的地方在于能否想到算法与背包问题的关系，一旦想通之后一切问题就会迎刃而解了。

比如力扣416分割等和子集，将其转化为背包容量为数组之和一半，并且物品的重量和价值相同的背包问题，如此便能够解决这个问题。

然后就是力扣1049最后一块石头的重量，这一题和上一题类似，想明白之后都是寻找最接近数组之和一半的值，也是转换为背包容量为数组之和一半，并且物品的重量和价值相同的背包问题。

最难的就是474一和零。这道题依然是每个元素只能使用一次，但是每个元素中有1和0两个值，因此按照简单的思路来考虑的话就只能使用三维数组来解决，横轴表示单个元素中的1的数量，纵轴表示单个元素中的2的数量，竖轴表示可选择元素的范围。想到之后依然不容易写，但是可以开始慢慢写了。

原文地址:https://blog.csdn.net/Zrf2191318455/article/details/136587367 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1766765453499305984.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部