01背包如何优化？
来提每日一题
2025-04-08 15:02:14
每天59秒拿下每日一题 北美求职 转码 程序员 互联网大厂 程序员日常 每日一题 编程 近期找工作现状
01背包。题目转换为选择若干个数，使得之和等于数组总和除以2；若数组总和为奇数直接返回false。记状态转移方程为dp[j]=dp[j] | dp[j-nums[i]]，初始时dp[0]=true，最后检查dp[总和一半]是否为真。这里可以使用bitset，初始第0位为1，加减操作等价于移位；即每次对bitset向右移位nums[i]然后取或运算，最后检查bitset中数组总和一半的二进制位是否为1。
看到这里都是真爱了，点个关注和赞吧[喝奶茶R]
0
阅读：1
