algorithm - C++ Chocolate Puzzle -

algorithm - C++ Chocolate Puzzle -

let's have n chocolates have packed p boxes in order arrive. each chocolate has number of calories x , each box has capacity k has less or equal 3*sum(x1, x2, ..., xn) + max(x1, x2, ..., xn)^2 - min(x1, x2, ..., xn)^2.

in task i'm given n, p , x each chocolate , have figure out lowest possible k. help me on (not looking solution hints regarding problem)?

example: n = 8, p = 3, x = {1, 4, 5, 6, 3, 2, 5, 3}

k first 3 chocolates = 3*(1+4+5) + 5^2 - 1^2 = 54 k next 2 chocolates = 3*(6+3) + 6^2 - 3^2 = 54 k lastly 3 chocolates = 3*(2+5+3) + 5^2 - 2^2 = 51 lowest possible k = 54

so goal find best combination using p boxes has lowest k.

thanks!

here how solve in 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]; (int = + 1; < to; i++) { sum += x [i]; max = math.max (max, x [i]); min = math.min (min, x [i]); } homecoming 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); } homecoming solution.intvalue (); } public static int dosolve (int n, int p, string signature) { if (p == 1) { bestmoves.put (signature, integer.valueof (x.length - n)); homecoming k (n, x.length); } else { int result = integer.max_value; int bestmove = 0; int maxi = x.length - n - p + 1; (int = 1; <= 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)); homecoming result; } } public static void main(string[] args) { int n = 20; int p = 5; x = new int [n]; random r = new random (); (int = 0; < n; i++) x [i] = r.nextint (9) + 1; system.out.println("n: " + n); system.out.println("p: " + p); system.out.print("x: {"); (int = 0; < 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; (int = p; > 0; i--) { int m = bestmoves.get (o + "," + i); system.out.print ("{"); (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); } }

probably find useful tips in code.

sample input:

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}

sample output:

{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

c++ algorithm puzzle