x*****3
发帖数: 447 | 1 被老婆缠着研究逛街买东西的计算，想请大家帮忙：
问题是常见的买100送30之类的时候，老婆想知道，在总额有限的情况下，比如她一共
买N件衣服，总价是M元，M=p1+p2......。假设优惠是每合计D元，就送d元。
这时候她需要计算，怎么样搭配价格，使得自己付出最少？有没有可能有一个通用计算
模式？
输入每件价格，得出最合算（也就是自己支付最少）的组合情况，能买齐所有衣服。
我自己想了下，也许可以说成下面这个题目，但是不完全贴切。
问题是这样的：
一个数列（p1,p2,p3......)共N个
当任意p1大于或等于D（任意正整数）时，p值增加一个常数值d，即p'=p+d.
当任意p1小于D时，使得p1+p2+...直到大于或等于D。那么这个小和p'也可增加一个常
数值d。
每个p只被加一次。
问题：p之间任意组合或相加，使得d值累计数=剩下没有相加的p值之和；并且p'最小。
需要设计一个这样能自动计算出最佳组合的模型。
请不吝指教！谢谢！ | v********e
发帖数: 1058 | 2 个人意见哈，题目就没说明白，后面的模型更是看得一头雾水……那什么p值什么，初
始值是什么，完全没看明白
题目里肯定有没说明白的地方，有什么限制条件漏掉了。我原来在北京买东西的时候想
过这个问题，现在也想不起细节了，印象中就是个线性规划。
【在 x*****3 的大作中提到】
: 被老婆缠着研究逛街买东西的计算，想请大家帮忙：
: 问题是常见的买100送30之类的时候，老婆想知道，在总额有限的情况下，比如她一共
: 买N件衣服，总价是M元，M=p1+p2......。假设优惠是每合计D元，就送d元。
: 这时候她需要计算，怎么样搭配价格，使得自己付出最少？有没有可能有一个通用计算
: 模式？
: 输入每件价格，得出最合算（也就是自己支付最少）的组合情况，能买齐所有衣服。
: 我自己想了下，也许可以说成下面这个题目，但是不完全贴切。
: 问题是这样的：
: 一个数列（p1,p2,p3......)共N个
: 当任意p1大于或等于D（任意正整数）时，p值增加一个常数值d，即p'=p+d.
| x*****3
发帖数: 447 | 3
那我把我老婆的原话大意说给你听啊：
一共买10件衣服，分别是80，113，45，.......之类的。假设一共是1080元。
但是商城会买100送80元代购劵。所以其实自己是不需要付1080元的，因为她准备先买
一部分的单，假设为6件600元，这些单的总价按照100送80的原则，累计了一个代购劵
的总数是480元，这个数刚好可以买剩下的4件衣服480元。
这样子清楚不？
现在把这个问题变成数学问题，怎样算出你支付的最小值？
【在 v********e 的大作中提到】
: 个人意见哈，题目就没说明白，后面的模型更是看得一头雾水……那什么p值什么，初
: 始值是什么，完全没看明白
: 题目里肯定有没说明白的地方，有什么限制条件漏掉了。我原来在北京买东西的时候想
: 过这个问题，现在也想不起细节了，印象中就是个线性规划。
| v********e
发帖数: 1058 | 4 整数规划：
已知：价格(p_1, p_2, ..., p_n)，买s元送t元
min \sum_{i=1}^{n} x_i p_i
s.t. (i) x_i = 0 or 1 for all i,
(ii) t * \sum_i {x_i p_i} >= s * \sum_i (1 - x_i) p_i.
输出(x_1, x_2, ..., x_n)
找个做整数规划的软件跑一跑就行了，现在没有多项式时间解，不过分枝定界一般能跑
得还可以了。可能可以更简单些，没细想。
【在 x*****3 的大作中提到】
:
: 那我把我老婆的原话大意说给你听啊：
: 一共买10件衣服，分别是80，113，45，.......之类的。假设一共是1080元。
: 但是商城会买100送80元代购劵。所以其实自己是不需要付1080元的，因为她准备先买
: 一部分的单，假设为6件600元，这些单的总价按照100送80的原则，累计了一个代购劵
: 的总数是480元，这个数刚好可以买剩下的4件衣服480元。
: 这样子清楚不？
: 现在把这个问题变成数学问题，怎样算出你支付的最小值？
| A*******r
发帖数: 768 | 5 给他2000元，自己打车回家
【在 x*****3 的大作中提到】
:
: 那我把我老婆的原话大意说给你听啊：
: 一共买10件衣服，分别是80，113，45，.......之类的。假设一共是1080元。
: 但是商城会买100送80元代购劵。所以其实自己是不需要付1080元的，因为她准备先买
: 一部分的单，假设为6件600元，这些单的总价按照100送80的原则，累计了一个代购劵
: 的总数是480元，这个数刚好可以买剩下的4件衣服480元。
: 这样子清楚不？
: 现在把这个问题变成数学问题，怎样算出你支付的最小值？
| x*****3
发帖数: 447 | 6
大侠能不能想个更简单的说法？
能不能做出excel的公式或者模型出来，输入单价后可以算出结果来？包子酬谢！
【在 v********e 的大作中提到】
: 整数规划：
: 已知：价格(p_1, p_2, ..., p_n)，买s元送t元
: min \sum_{i=1}^{n} x_i p_i
: s.t. (i) x_i = 0 or 1 for all i,
: (ii) t * \sum_i {x_i p_i} >= s * \sum_i (1 - x_i) p_i.
: 输出(x_1, x_2, ..., x_n)
: 找个做整数规划的软件跑一跑就行了，现在没有多项式时间解，不过分枝定界一般能跑
: 得还可以了。可能可以更简单些，没细想。
| s*x
发帖数: 3328 | 7 这个问题如果不要求整数的话很简单，但是如果要按离散问题来算就比较麻烦，但是如
果不要求最优解，只要求一个k-approximation解的话应该不难，弄个greedy算法，估
计就是个k-approximation，我猜想这个k\leq 2. 算法大概如下：
把 p_1\cdots p_n 按价格由大到小排序，然后从p_1开始加一直到p_n，如果其中加入
某件商品超过了100块，就不加那件商品。最后加剩下的商品价值最小的。这些买下来
。然后第二轮开始，还是类似的做法。直到最后没有剩下的了。
比如如下7件商品 100,40,40,40,30,20,10
第一次 100+10 送 30, 剩下 40,40,40,30,20
第二次 40+40+20 送 30, 剩下 30
第三次 30
【在 x*****3 的大作中提到】
: 被老婆缠着研究逛街买东西的计算，想请大家帮忙：
: 问题是常见的买100送30之类的时候，老婆想知道，在总额有限的情况下，比如她一共
: 买N件衣服，总价是M元，M=p1+p2......。假设优惠是每合计D元，就送d元。
: 这时候她需要计算，怎么样搭配价格，使得自己付出最少？有没有可能有一个通用计算
: 模式？
: 输入每件价格，得出最合算（也就是自己支付最少）的组合情况，能买齐所有衣服。
: 我自己想了下，也许可以说成下面这个题目，但是不完全贴切。
: 问题是这样的：
: 一个数列（p1,p2,p3......)共N个
: 当任意p1大于或等于D（任意正整数）时，p值增加一个常数值d，即p'=p+d.
| v********e
发帖数: 1058 | 8 其实商品价格低的话可以用动态规划的，但是复杂度跟价格相关而不是价格的字节数相关
【在 s*x 的大作中提到】
: 这个问题如果不要求整数的话很简单，但是如果要按离散问题来算就比较麻烦，但是如
: 果不要求最优解，只要求一个k-approximation解的话应该不难，弄个greedy算法，估
: 计就是个k-approximation，我猜想这个k\leq 2. 算法大概如下：
: 把 p_1\cdots p_n 按价格由大到小排序，然后从p_1开始加一直到p_n，如果其中加入
: 某件商品超过了100块，就不加那件商品。最后加剩下的商品价值最小的。这些买下来
: 。然后第二轮开始，还是类似的做法。直到最后没有剩下的了。
: 比如如下7件商品 100,40,40,40,30,20,10
: 第一次 100+10 送 30, 剩下 40,40,40,30,20
: 第二次 40+40+20 送 30, 剩下 30
: 第三次 30
| n******t
发帖数: 4406 | 9 肯定没几件衣服，就用IP就万事了。
要买几千件衣服的，也不会省成这样了。
【在 s*x 的大作中提到】
: 这个问题如果不要求整数的话很简单，但是如果要按离散问题来算就比较麻烦，但是如
: 果不要求最优解，只要求一个k-approximation解的话应该不难，弄个greedy算法，估
: 计就是个k-approximation，我猜想这个k\leq 2. 算法大概如下：
: 把 p_1\cdots p_n 按价格由大到小排序，然后从p_1开始加一直到p_n，如果其中加入
: 某件商品超过了100块，就不加那件商品。最后加剩下的商品价值最小的。这些买下来
: 。然后第二轮开始，还是类似的做法。直到最后没有剩下的了。
: 比如如下7件商品 100,40,40,40,30,20,10
: 第一次 100+10 送 30, 剩下 40,40,40,30,20
: 第二次 40+40+20 送 30, 剩下 30
: 第三次 30
|
|
