-5

到着順に正確に P​​ 個の箱に詰めなければならない N 個のチョコレートがあるとします。各チョコレートにはカロリー数 X があり、各箱の容量 K は 3*sum(x1, x2, ..., xn) + max(x1, x2, ..., xn)^2 - min(x1, x2, ..., xn)^2.

タスクでは、チョコレートごとに N、P、X が与えられ、可能な限り低い K を計算する必要があります。これについて誰か助けてもらえますか (問題に関するいくつかのヒントのためだけに解決策を探すのではなく)。

例: N = 8、P = 3、X = {1、4、5、6、3、2、5、3}

K for first three chocolates = 3*(1+4+5) + 5^2 - 1^2 = 54
K for next two chocolates = 3*(6+3) + 6^2 - 3^2 = 54
K for last three chocolates = 3*(2+5+3) + 5^2 - 2^2  = 51

Lowest possible K = 54

したがって、目標は、最小の K を持つ正確に P​​ 個のボックスを使用して、最適な組み合わせを見つけることです。

ありがとう！

4

1 に答える 1

1

これをJavaで解決する方法は次のとおりです。

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class ChocolatePuzzle {
    private static final Map <String, Integer> solutions =
        new HashMap <String, Integer> ();

    private static final Map <String, Integer> bestMoves =
            new HashMap <String, Integer> ();

    private static int [] x;

    private static int k (int from, int to)
    {
        int sum = x [from];
        int max = x [from];
        int min = x [from];
        for (int i = from + 1; i < to; i++)
        {
            sum += x [i];
            max = Math.max (max, x [i]);
            min = Math.min (min, x [i]);
        }

        return sum * 3 + max * max - min * min;
    }

    public static int solve (int n, int p)
    {
        String signature = n + "," + p;
        Integer solution = solutions.get (signature);
        if (solution == null)
        {
            solution = Integer.valueOf (doSolve (n, p, signature));
            solutions.put (signature, solution);
        }
        return solution.intValue ();
    }

    public static int doSolve (int n, int p, String signature)
    {
        if (p == 1)
        {
            bestMoves.put (signature, Integer.valueOf (x.length - n));
            return k (n, x.length);
        }
        else
        {
            int result = Integer.MAX_VALUE;
            int bestMove = 0;

            int maxI = x.length - n - p + 1;
            for (int i = 1; i <= maxI; i++)
            {
                int k = Math.max (k (n, n + i), solve (n + i, p - 1));

                if (k < result)
                {
                    result = k;
                    bestMove = i;
                }
            }

            bestMoves.put (signature, Integer.valueOf (bestMove));

            return result;
        }
    }

    public static void main(String[] args) {
        int n = 20;
        int p = 5;
        x = new int [n];

        Random r = new Random ();
        for (int i = 0; i < n; i++)
            x [i] = r.nextInt (9) + 1;

        System.out.println("N: " + n);
        System.out.println("P: " + p);
        System.out.print("X: {");
        for (int i = 0; i < n; i++)
        {
            if (i > 0) System.out.print (", ");
            System.out.print (x [i]);
        }
        System.out.println("}");

        System.out.println();

        int k = solve (0, p);

        int o = 0;
        for (int i = p; i > 0; i--)
        {
            int m = bestMoves.get (o + "," + i);

            System.out.print ("{");
            for (int j = 0; j < m; j++)
            {
                if (j > 0)
                    System.out.print (", ");
                System.out.print (x [o + j]);
            }
            System.out.print ("} (k: ");
            System.out.print(k (o, o + m));
            System.out.println (")");

            o += m;
        }

        System.out.println("min(k): " + k);
    }
}

おそらく、このコードでいくつかの役立つヒントを見つけることができます。

サンプル入力：

N: 20
P: 5
X: {1, 7, 6, 6, 5, 5, 7, 9, 1, 3, 9, 5, 3, 7, 9, 1, 4, 2, 4, 8}

サンプル出力：

{1, 7, 6, 6} (k: 108)
{5, 5, 7, 9} (k: 134)
{1, 3, 9, 5} (k: 134)
{3, 7, 9} (k: 129)
{1, 4, 2, 4, 8} (k: 120)
min(k): 134
于 2013-02-20T10:26:57.147 に答える