ahaxzh
V2EX  ›  算法

鉴于/t/779528 想不明白,想再咨询一个问题

  •  
  •   ahaxzh · May 29, 2021 · 1347 views
    This topic created in 1823 days ago, the information mentioned may be changed or developed.

    原始需求: /t/779528

    鉴于这个问题我想不太明白,我想咨询另一个算法问题,算是曲线解决吧!

    问题描述:

    1 、给定数列 An[a1,a2......an] ,an 为不重复数据,数列里数量 n 不固定,且每个数字都有一个权重 s 。 给定数字 X,X 大于 An 里的任意数字。

    2 、求: 所有给定数列里 的数字 相加 组合 小于等于 X 且 大于 X * 90% 的 所有结果,按照 权重合计 排序输出。

    3 、这个问题是我自己想的,我其实是想打一张表,表里涵盖所有情况

    4 、值得注意的是 an 可以重复, 比如 an + an + ..... 也是允许的

    Eg:

    An[1,2,3,4,5,6,7,8,9,10]

    Sn[1,2,3,4,5,6,7,8,9,10]

    X = 100

    那权重最低的情况应该是 1 * 100,权重第二低的是 1* 98 + 2, 第三的是 1* 97 + 2 。

    奈何 不管是 36 ! 还是 2^36 时空复杂度都太高了。

    No Comments Yet
    About   ·   Help   ·   Advertise   ·   Blog   ·   API   ·   FAQ   ·   Solana   ·   3345 Online   Highest 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 35ms · UTC 11:03 · PVG 19:03 · LAX 04:03 · JFK 07:03
    ♥ Do have faith in what you're doing.