python-查找是否存在满足不等式的n / 2个元素的子集之和？

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了python-查找是否存在满足不等式的n / 2个元素的子集之和？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4321字，纯文字阅读大概需要7分钟。

内容图文

给定这些测试用例：

votes = [6]*28
m = 10

votes1 = [5]*28+[6]*2
m1 = 10

votes2 = [5]*29+[10]*1
m2 = 10

votes3 =  [8, 8, 16, 12, 12, 12, 4, 4, 12, 4, 4, 4, 8, 12, 12, 8, 8, 16, 12, 4, 16, 16, 12, 16, 12, 16, 12, 4, 16, 4, 4, 12, 4, 12, 12, 4, 16, 12, 16, 8]
m3 =  20

votes4 =  [22, 21, 34, 39, 28, 33, 32, 40, 22, 34, 36, 27, 37, 34, 40, 38, 39, 32, 37, 40, 31, 37, 22, 21, 35, 34, 24, 40, 34, 21, 24, 20, 30, 31, 22, 30, 31, 25, 20, 38, 24, 23, 32, 27, 20, 31, 27, 32, 22, 32, 33, 34, 40, 38, 36, 29, 34, 24, 24, 39, 32, 37, 30, 20, 29, 26, 36, 40, 34, 22, 30, 27, 38, 27, 26, 28, 23, 40, 31, 22, 23, 35, 23, 31, 23, 39, 30, 20, 20, 35, 27, 23, 23, 29, 40, 20, 34, 40, 28, 25]
m4 =  50

votes5 =  [25, 25, 25, 24, 25, 24, 24, 25, 26, 25, 26, 24, 25, 26, 24, 26, 24, 26, 26, 25, 26, 24, 26, 24, 26, 26, 26, 25, 25, 26, 24, 26, 25, 25, 24, 25, 25, 26, 26, 26, 25, 26, 25, 26, 25, 25, 24, 24, 24, 25, 24, 26, 25, 24, 26, 24, 24, 26, 24, 26, 24, 24, 24, 26, 24, 25, 24, 26, 25, 25, 26, 25, 25, 25, 25, 26, 25, 24, 25, 25, 24, 24, 24, 26, 26, 26, 25, 24, 25, 25, 25, 26, 25, 24, 26, 24, 25, 26, 24, 26]
m5 =  50

给定以下界限：

def upperbound(v, m, n):
    return math.floor(v - 0.25 * m * n - 1)


def lowerbound(m, n):
    return math.ceil(0.25 * m * n + 1)

我想找到是否有总长度为len(votes)/ 2的子集的总和可以满足给定的上限和下限.

以下是我尝试使用背包解决问题的尝试,但并未考虑子集的长度.

import math


def winnable(votes, m):
    n = len(votes)  # Number of columns
    v = sum(votes)
    ub = upperbound(v, m, n)
    lb = lowerbound(m, n)

    max_possible = knapSack(ub, votes, n)

    if max_possible < lb:
        return "not possible"
    else:
        return "possible"


def knapSack(ub, val, n):
    K = [[0 for x in range(ub + 1)] for x in range(n + 1)]

    # Build table K[][] in bottom up manner
    for i in range(n + 1):
        for w in range(ub + 1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif val[i - 1] <= w:
                K[i][w] = max(val[i - 1] + K[i - 1][w - val[i - 1]], K[i - 1][w])
            else:
                K[i][w] = K[i - 1][w]

    return K[n][ub]

是否可以进一步修改我的解决方案以考虑子集中元素的数量.

解决方法:

我已经实现了@mrmcgreg的建议,为该问题添加了更多的维度

import math

def has_valid_subset(votes, m):
    n = len(votes)
    sum_min = math.ceil(0.25 * m * n + 1)
    sum_max = math.floor(sum(votes) - 0.25 * m * n - 1)
    n_half = n // 2
    K = [[[(False, 0) for elements in range(min(n_half + 1, index + 1))]
          for index  in range(len(votes) + 1)]
         for weight in range(sum_max + 1)]
    for weight in range(sum_max + 1):
        for index in range(len(votes) + 1):
            if index == 0:
                K[weight][index][0] = (True, 0)
                continue
            v = votes[index - 1]
            for elements in range(min(n_half + 1, index)):
                if v > weight:
                    K[weight][index][elements] = K[weight][index - 1][elements]
                else:
                    skip_ok, skip_w = K[weight][index - 1][elements]
                    add_ok, add_prev_w = K[weight - v][index - 1][elements - 1]
                    add_w = add_prev_w + v
                    if skip_ok and add_ok:
                        K[weight][index][elements] = (True, max(skip_w, add_w))
                    elif skip_ok:
                        K[weight][index][elements] = (True, skip_w)
                    elif add_ok:
                        K[weight][index][elements] = (True, add_w)
    b_max, w_max = K[-1][-1][-1]
    if not b_max:
        return False
    return w_max >= sum_min

测试：

votes = [6]*28
m = 10
print(has_valid_subset(votes, m))
# True

votes1 = [5]*28+[6]*2
m1 = 10
print(has_valid_subset(votes1, m1))
# True

votes2 = [5]*29+[10]*1
m2 = 10
print(has_valid_subset(votes2, m2))
# False

votes3 =  [8, 8, 16, 12, 12, 12, 4, 4, 12, 4, 4, 4, 8, 12, 12, 8, 8, 16, 12, 4, 16, 16, 12, 16, 12, 16, 12, 4, 16, 4, 4, 12, 4, 12, 12, 4, 16, 12, 16, 8]
m3 =  20
print(has_valid_subset(votes3, m3))
# False

votes4 =  [22, 21, 34, 39, 28, 33, 32, 40, 22, 34, 36, 27, 37, 34, 40, 38, 39, 32, 37, 40, 31, 37, 22, 21, 35, 34, 24, 40, 34, 21, 24, 20, 30, 31, 22, 30, 31, 25, 20, 38, 24, 23, 32, 27, 20, 31, 27, 32, 22, 32, 33, 34, 40, 38, 36, 29, 34, 24, 24, 39, 32, 37, 30, 20, 29, 26, 36, 40, 34, 22, 30, 27, 38, 27, 26, 28, 23, 40, 31, 22, 23, 35, 23, 31, 23, 39, 30, 20, 20, 35, 27, 23, 23, 29, 40, 20, 34, 40, 28, 25]
m4 =  50
print(has_valid_subset(votes4, m4))
# True

votes5 =  [25, 25, 25, 24, 25, 24, 24, 25, 26, 25, 26, 24, 25, 26, 24, 26, 24, 26, 26, 25, 26, 24, 26, 24, 26, 26, 26, 25, 25, 26, 24, 26, 25, 25, 24, 25, 25, 26, 26, 26, 25, 26, 25, 26, 25, 25, 24, 24, 24, 25, 24, 26, 25, 24, 26, 24, 24, 26, 24, 26, 24, 24, 24, 26, 24, 25, 24, 26, 25, 25, 26, 25, 25, 25, 25, 26, 25, 24, 25, 25, 24, 24, 24, 26, 26, 26, 25, 24, 25, 25, 25, 26, 25, 24, 26, 24, 25, 26, 24, 26]
m5 =  50
print(has_valid_subset(votes5, m5))
# True

内容总结

以上是互联网集市为您收集整理的python-查找是否存在满足不等式的n / 2个元素的子集之和？全部内容，希望文章能够帮你解决python-查找是否存在满足不等式的n / 2个元素的子集之和？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端