二维数组,首项和确定,求第二项和的最大值

小狗快跑嘟嘟
  • 2.8k

有如下数组

items = [[1,10], [3,15], [4,12], [2,9], [3, 17] ....]

从items中取出4个,要求item[0]和为10,求item[1]和的最大值。

有无最优解?

回复
阅读 2.8k
3 个回答

思路:由于items[0]的总和很小且,把背包容量视为4,暴力枚举items[0]和一样时,items[1]和的最优值。

#include<iostream>
#include <cstdlib>

using namespace std;

struct item
{
    int k,v;
}items[9]={{1,10},{3,15},{4,12},{2,9},{3,17},{5,1},{7,22},{2,8},{4,6}};

int a[3][11];
int ans;
int main()
{
    ios::sync_with_stdio(false);

    for(int i(0); i != 9; ++i)
    {
        if(items[i].k < 11 && a[2][10 - items[i].k] && a[2][10 - items[i].k] + items[i].v > ans)
        {
            ans = a[2][10 - items[i].k] + items[i].v;
        }
        for(int j(1); j > -1; --j)
        {
            for(int k(10 - items[i].k); k > -1; k--)
            {
                if(a[j][k] && a[j + 1][k + items[i].k] < a[j][k] + items[i].v)
                {
                    a[j + 1][k + items[i].k] = a[j][k] + items[i].v;
                }
            }
        }
        if(a[0][items[i].k] < items[i].v)
        {
            a[0][items[i].k] = items[i].v;
        }
    }

    cout << ans << endl;

    return EXIT_SUCCESS;
}

我的算法有问题,不能算出最优答案。
假设有2组结果首项和都为10,且第二项升序排列。
A : 1 3 5 7
B : 2 3 4 7
根据我的算法,会得到A结果,但是无法保证
1+3+5+7 > 2+3+4+7=>1+5 > 2+4


# coding=utf-8
def func():
    items = [[1,10], [3,15], [4,12], [2,9], [3, 17], [5, 1], [7, 22], [2, 8], [4, 6]]
    # 按照item[1]降序排列
    items = sorted(items, key=lambda item: item[1])
    print(findMaxItems(10,items,4))

def findMaxItems(sum,items,count):
    if sum <= 0:
        return []

    if count == 1:
        return findMaxItem(sum,items)
    
    while len(items) > 0:
        item = items.pop()
        left_items = findMaxItems(sum - item[0],items[:],count - 1)
        
        if len(left_items) == (count - 1):
            left_items.append(item)
            return left_items
    return []

def findMaxItem(value,items):
    max = None;
    for item in items:
        if item[0] == value:
            if max == None or item[1] > max[1]:
                max = item
    if max == None:
        result = []
    else:
        result = [max]
    return result

func()

输出结果:

[[2, 8], [2, 9], [3, 15], [3, 17]]

由于思路停留在背包问题,代码确实出现了bug,即数量4满足,但总和为10并没有满足,实际情况是<=10……


原答案:

这个问题看似是个背包问题,实则比背包的条件更加苛刻。

每个item的两个数可以分别对应背包问题里的weight(重量)value(价值),但与背包不同的是:

1.众多item只能选4个,即背包里只能装4个物品。
2.总重量严格要求等于10,而非小于等于10

所以传统的动态规划和贪心算法我暂时没能想到对应的解法,我这里给出一段算法,借鉴了贪心的思路,但有所不同:

1.将items按照item[1]的大小降序排列。
2.遍历items,并计算取得的item[0]的和,若大于10continue,否则添加斤最终结果result中,直到取出4个。

呃,不过说实话,我对自己这段代码【没有信心,不能保证最优解】,只是一个思路,所以还请其他诸位大神多提提意见。^0^

以下是代码:

# coding=utf-8
# python2.7.9
def func():
    items = [[1,10], [3,15], [4,12], [2,9], [3, 17], [5, 1], [7, 22], [2, 8], [4, 6]]
    # 按照item[1]降序排列
    items = sorted(items, key=lambda item: item[1], reverse=True)
    result = []
    # 总和
    total = 10
    # 总数
    count = 4
    for item in items:
        # item[0]的最大取值
        limit = total - count
        if item[0] > limit:
            continue
        result.append(item)
        total = total - item[0]
        count = 4 - len(result)
        if count < 1 or total < 1:
            break
    print result

func()

输出结果:

[[3, 17], [3, 15], [1, 10], [2, 9]]
撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏