I am trying to find a non-adaptive greedy algorithm for the following problem :

The input is a set of cards and an integer C. Each card has a digit d and a cost c. A solution is a subset of the cards in an order. The solution is valid if the sum of the costs of the cards is at most C. Consider the string D formed by concatenating the digits of the solution together with zeros added on the end so that each solution has n characters. The value of the solution which we are to maximize is the integer value and/or the lexicographical order of D.

For example, here is an input I = {<2,5>, <3,4>, <3,3>, …, <3,3>, <8,8>, <9,9>, <9,10>} and C = 14. The following are the D and total cost C’ for various valid solutions sorted from worst to best:

D = 833000000 —– C’ = 8 + 3 + 3 = 14 —- S = {<8,8>, <3,3>, <3,3>}

D = 930000000 —– C’ = 9 + 3 = 12 —- S = {<9,9> <3,3>}

D = 930000000 —– C’ = 9 + 4 = 13 —- S = {<9,9> <3,4>}

D = 930000000 —– C’ = 10 + 4 = 14 —- S = {<9,10> <3,4>}

I was thinking of an algorithm that first sort the input cards in descending order according to their digits and their costs then choose the card with largest digit as long as the addition of its cost and total cost C’ doesn’t exceed C. What do you think ?