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++巧克力拼圖

回答

相關問題