-3

number 、 number xのリスト、および max number があるとしyます。合計が0を超えたり0を下回ったりしxないように、リスト内の各要素の加算または減算から得られる最大の結果を見つける必要があります。y

注: リスト内の各要素を加算または減算する必要があります。つまり、数字をスキップすることはできません。

例：

x= 3 y=10  list={2,6,1}

Max i can get :3 - 2 + 6 +1 = 8 これは 10 未満であり、>0 の
失敗ケースは、3+2+6+1= 12 which が > y であるため、無効なソリューションです。
別の失敗例 3-2-6 = -5 (拒否された -ve 番号を取得したため、ここでは 6 の後の要素をチェックする必要はありません)

この最大値を見つけるにはどうすればよいですか?

4

2 に答える 2

3

したがって、基本的に listlと numberがあり (と gety-xを加算する必要がある場合は、 getと同等であることが簡単にわかります)、各要素を加算/減算して、 value にできるだけ近づけたいとします。xyy-xly-x

この問題はNP-CompleteであるPartition Problemと同等であることに注意してください。これは、 listがあり、 - のような値がある場合、、およびこれがまさにパーティションの問題である2 つのサブリストを見つける必要があるためです。ly-x == 0l1,l2sum(l1) - sum(l2) == 0l1 union l2 = l

したがって、問題に対する既知の多項式解はありません。

関連するサブセット合計問題の疑似多項式 DP ソリューションのバリエーション、または指数関数的 (バックトラッキングなど) ソリューションを検討したいと思います。

于 2012-11-12T21:56:15.653 に答える
0

解決策は次のとおりです。

    int x = 3, y = 10;
    var lst = new List<int>{ 1, 2, 3, 4 };
    int n = (int)Math.Pow(2, lst.Count);
    var lst2 = new List<List<int>>();
    for (int i = 0; i < n; i++)
    {
        var lstCopy = new int[lst.Count];
        lst.CopyTo(lstCopy);
        for (int j = 1; j <= i; j *= 2)
            if ((j & i) != 0)
                lstCopy[(int)Math.Log(j, 2)] *= -1;
        lst2.Add(lstCopy.ToList());
    }
    bool yes = lst2.Select(l=>x + l.Sum()).Any(l=>l > 0 && l < y);
    if (yes)
        Console.WriteLine(lst2.Select(l => x + l.Sum()).Where(l => l > 0 && l < y).First());

ここで、整数の 2^n 配列をチェックする必要があることに注意してください。ここで、n は元の配列の長さです ({2, 6, 1} です)。

于 2012-11-12T22:18:06.243 に答える