I think what is wanted is a k-means algorithm or something similar for optimizing the cost. Let's look at it in terms of packing books.
I am able to order k boxes for packing my (long) shelf of n books. Many aspects of my order have low cost, but one aspect which I want to optimize is space-height. So when I pack books in a box, the books should all be about the same height; I can pad or adjust for depth and width cheaply, but I need to get the height optimally arranged for my order of boxes.
How do I organize the books? I arrange them in order from smallest to largest height, then I make divisions into k groups of equal numbers of books to start. Then I compute the cost of ordering k boxes for this grouping as a threshold. Then for each book which is the tallest or shortest in the group, I shift it from one stack to an adjoining stack, and recompute my cost function. If I lower the cost by moving the book, the book gets assigned to the new stack.
I iterate this (moving an end book from one stack to an adjacent stack) among the k stacks until I achieve a satisfactory optimum. This is not quite a k-means clustering algorithm, but it shows the basic idea.
For the stated problem, it might be useful to go one of two ways: have the cost function (aA+bB+cC) be the "height" of the book that is the value to do the k-means clustering, or (since the original algorithm worked on grouping n-dimensional data points into clusters) work on grouping the triples into clusters, and then applying the cost function and massage the clusters for improved solutions.
I do not claim that this is the best or most efficient algorithm for this problem. However, k-means clustering seems to be the natural approach (even though a local sup, not a mean or average, is wanted).
Gerhard "Applying Himself To Applied Math" Paseman, 2018.08.18.