首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >买最合适的东西

问买最合适的东西
EN

Code Golf用户
提问于 2019-03-04 11:31:43
回答 2查看 337关注 0票数 6

一家商店正在大减价。如果你方价格达到199美元或更多,你可以降低100美元。You只能购买每种产品一次。下面是一个产品示例列表:(为了简化,产品名称用字母表示)

代码语言:javascript
复制
+------+-------+
| name | price |
+------+-------+
| A    | 26.9  |
| B    | 24.9  |
| C    | 49.9  |
| D    | 28.9  |
| E    | 14.9  |
| F    | 16.9  |
| G    | 19.9  |
| H    | 19    |
| I    | 14.9  |
| J    | 14.9  |
| K    | 26.9  |
+------+-------+

输入

  • 一个产品价格清单,如上面的例子。
  • N项目列表大小10 <= N <= 100
  • X a价格

输出

省钱的最佳购物策略。找出总价格高于X的最便宜的购买清单,并输出:

  • 对于上述数据,最合适的总价(扣除前)是X =199美元,最合适的总价是199.2。

Notes

  • 您的代码可以是函数(方法)或完整的工作程序。
  • 使您的算法as尽可能快地(减少时间复杂度)!
  • 如果代码具有相同的时间复杂度,那么使用较少空间的代码将获胜。
EN

回答 2

Code Golf用户

回答已采纳

发布于 2019-03-05 09:41:14

Python 2,O(2^{n/2})

代码语言:javascript
复制
import sys
def subsetsum(nums, target):
#    totalsum = sum(nums)
#    if(totalsum == target):
#        return target
#    if(totalsum < target):
#        return -1

    sumsA = {}
    sumsB = {}
    for n in nums[::2]:
        for k,v in sumsA.items() + [(0,[])]:
            newsum = k + n
            if newsum not in sumsA:
                sumsA[newsum] = v + [n]
                if newsum == target:
                    print "target found in sumsA loop: "
                    return target
    minsum = sys.maxsize
    for n in nums[1::2]:
        for k,v in sumsB.items() + [(0,[])]:
            newsum = k + n
            if newsum not in sumsB:
                sumsB[newsum] = v + [n]
                if newsum == target:
                    print "target found in sumsB loop: "
                    return target
                for a in sumsA:
                    combsum = a + newsum
                    if combsum == target:
                        print "target found in combined sumsA and sumsB loop: "
                        return target
                    if combsum > target and combsum < minsum:
                        minsum = combsum
    print "target",target,"not found, so return the closest alternative: "
    return minsum

# Test cases:
print subsetsum([26.9, 24.9, 49.9, 28.9, 14.9, 16.9, 19.9, 19, 14.9, 14.9, 26.9], 199)
print subsetsum([47.5, 1.0, 19.6, 16.7, 21.8, 5.6, 40.4, 31.8, 25.4, 21.9,
                 21.7, 17.6, 48.4, 17.4, 41.1, 8.9, 12.2, 25.6, 28.5, 26.3,
                 21.3, 35.1, 37.8, 45.1, 28.5, 47.6, 33.9, 21.5, 34.3, 14.2,
                 40.9, 17.9, 44.9, 44.2, 20.5, 30.8, 43.0, 24.5, 20.1, 46.7,
                 49.6, 42.1, 19.8, 3.8, 0.2, 38.3, 21.3, 15.3, 11.2, 36.0], 1000)
print subsetsum([47.5, 1.0, 19.6, 16.7, 21.8, 5.6, 40.4, 31.8, 25.4, 21.9,
                 21.7, 17.6, 48.4, 17.4, 41.1, 8.9, 12.2, 25.6, 28.5, 26.3,
                 21.3, 35.1, 37.8, 45.1, 28.5, 47.6, 33.9, 21.5, 34.3, 14.2,
                 40.9, 17.9, 44.9, 44.2, 20.5, 30.8, 43.0, 24.5, 20.1, 46.7,
                 49.6, 42.1, 19.8, 3.8, 0.2, 38.3, 21.3, 15.3, 11.2, 36.0], 555.5)

在网上试试。

我的Python技巧有点生疏,所以如果你看到任何问题,请告诉我。此外,我认为可以通过一些二进制搜索或类似的方法,在代码中对此进行改进。

该程序使用背包会合中法。它首先使用所有偶数索引项为这些偶数索引项的powerset获取一组可能的总和。然后,它对所有奇数索引项做相同的操作,同时使用这两个集合的和来确定最小和。

票数 2
EN

Code Golf用户

发布于 2019-03-04 22:20:29

果冻,10字节,得分O(2^n)

代码语言:javascript
复制
ŒPS€>Ƈ199Ṃ

在网上试试!

输入是商品的价格清单。产量是大于199的最低可能价格。注意,由于浮点四舍五入,这将输出199.20000000000002。另外,请注意,它的最低总价格将大于199 (而不是大于或等于)。

所用时间呈指数级,与2^n近似成正比,其中n是项目数。在TIO上,大约有19项。14.5秒

票数 0
EN
页面原文内容由Code Golf提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://codegolf.stackexchange.com/questions/180841

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档