[算法][动态规划]背包问题变体-均分礼物

本文主要是介绍[算法][动态规划]背包问题变体-均分礼物，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

均分礼物

今天遇到的一个面试手撕题：

给定一个礼物价值清单，需要将其进行划分为两个子集，以使得两个子集的价值和的差值最小。

思路

[算法][动态规划][背包问题①]0-1背包问题的优化及约束变形[python实现

1. 将其视为一个0-1背包问题
2. 取总价值的一半作为背包容量
3. 尽量填满这个背包(此问题中$w_i$=$v_i$)

d p [ j ] = m a x { d p

这篇关于[算法][动态规划]背包问题变体-均分礼物的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---