C++巧克力拼图

-5

比方说，我有N个巧克力必须按照它们到达的顺序包装到P盒中。每个巧克力还具有许多卡路里X，并且每个盒子具有必须小于或等于3 * sum（x1，x2，...，xn）+ max（x1，x2，...， xn）^ 2 - min（x1，x2，...，xn）^ 2。C++巧克力拼图

在任务中我给每个巧克力的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

所以目标是找到最好的组合使用完全P盒，具有最低的K.

谢谢！

来源

2013-02-20 Tuntuni

这看起来像一个家庭作业的问题。此外，你会想把它标记为“算法”。这不是特定于语言的。最后但并非最不重要的是，这看起来像贪婪策略的二元搜索问题。 – phoeagon 2013-02-20 09:48:58

这是，但我不知道如何解决它。你能否给我多些提示？ – Tuntuni 2013-02-20 10:17:09

对我来说，这看起来像是在TopCoder比赛中很常见的“动态编程”任务。 – 2013-02-20 11:09:30

这是我怎么会在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-20 10:26:57

C++巧克力拼图

回答

相关问题