3
$\begingroup$

In the game of 20-card games, the objective is to select a card or pass on it at every turn, with the goal of maximizing the sum of the numbers on the chosen cards. You have knowledge of the numbers on all cards for the entire game and We know the order in which they will appear. However, there is one rule to keep in mind: if you choose four cards in consecutive turns, you must pass on the following two cards. This is the only rule in the game.

The numbers will come in this order:

$5,3,5,4,8,7,6,6,10,15,13,14,15,5,3,6,6,8,9,7$

To illustrate the rule more clearly, if you select 5, 3, 5, 4, then you must skip the next two cards, which are 8 and 7.

So,

What is the highest possible total that can be obtained from these numbers and their arrangement with the given rule?

and the second question is that

What is the highest possible total that can be obtained from these numbers if you play the game with the same 5 decks in a row with the same orders coming after and after?

For example,

5,3,5,4,8,7,6,6,10,15,13,14,15,5,3,6,6,8,9,7,5,3,5,4,8,7,6....,6,9,8,7.

in total 100 numbers.

$\endgroup$
4
  • 2
    $\begingroup$ Bonus Question should be posted as a separate, follow-up question. $\endgroup$ Commented Jan 28, 2023 at 16:21
  • $\begingroup$ I can't immediately see that there's a general non-bruteforce method to solving this, but that may just be my poor eyesight. Did you have a clever approach in mind, or is this intended as a programming exercise? $\endgroup$
    – Bass
    Commented Jan 28, 2023 at 23:40
  • $\begingroup$ @Bass The dynamic programming approach I described could reasonably be computed by hand for $n=20$. $\endgroup$
    – RobPratt
    Commented Jan 29, 2023 at 0:46
  • $\begingroup$ @Bass you do not have to solve by brute borce the first part at least. I believed this would be interesting problem for everyone since it requires different way of thinking (please check v2) $\endgroup$
    – Oray
    Commented Jan 29, 2023 at 8:06

1 Answer 1

3
$\begingroup$

Let $r_i$ be the reward for selecting card $i$. You can solve the problem via integer linear programming as follows. Let binary decision variable $x_i$ indicate whether card $i$ is selected. The problem is to maximize $\sum_i r_i x_i$ subject to linear constraints \begin{align} \sum_{j=i}^{i+3} x_j + x_{i+4} &\le 4 &&\text{for all $i$} \tag1\label1\\ \sum_{j=i}^{i+3} x_j + x_{i+5} &\le 4 &&\text{for all $i$} \tag2\label2\\ \end{align} Constraint \eqref{1} enforces $\bigwedge_{j=i}^{i+3} x_j \implies \lnot x_{i+4}$, and constraint \eqref{2} enforces $\bigwedge_{j=i}^{i+3} x_j \implies \lnot x_{i+5}$

For the $20$-card problem, the maximum is

125, achieved by selecting the following cards (1 = select, 0 = do not select)

11101110111011101111

For the $100$-card problem, the maximum is

600, achieved by

1110110111011101110111011101110111011011101110110111100110111011101101111001011101101110111011101111


Alternatively, you can use dynamic programming. Let value function $V(i,k)$ be the maximum sum over cards $i,\dots,n$ if there are $k$ cards in the current run. You want to compute $V(1,0)$. The DP recursion is $$V(i,k) = \begin{cases} \max(r_i + V(i+1,k+1), V(i+1,0)) &\text{if $k < 3$}\\ \max(r_i + V(i+3,0), V(i+1,0)) &\text{if $k = 3$}\\ \end{cases} $$ Here's the resulting table of $V(i,k)$ values for $n=20$: \begin{matrix} i \backslash k & 0 & 1 & 2 & 3 \\ \hline 1 & \color{red}{125} & 122 & 122 & 120 \\ 2 & 120 & 120 & 117 & 117 \\ 3 & 117 & 117 & 117 & 114 \\ 4 & 114 & 112 & 112 & 112 \\ 5 & 112 & 110 & 107 & 106 \\ 6 & 106 & 104 & 102 & 99 \\ 7 & 99 & 99 & 97 & 95 \\ 8 & 95 & 93 & 93 & 91 \\ 9 & 91 & 89 & 87 & 87 \\ 10 & 87 & 81 & 79 & 77 \\ 11 & 77 & 72 & 66 & 64 \\ 12 & 64 & 64 & 59 & 53 \\ 13 & 53 & 50 & 50 & 45 \\ 14 & 38 & 38 & 35 & 35 \\ 15 & 33 & 33 & 33 & 30 \\ 16 & 30 & 30 & 30 & 30 \\ 17 & 30 & 24 & 24 & 24 \\ 18 & 24 & 24 & 17 & 16 \\ 19 & 16 & 16 & 16 & 9 \\ 20 & 7 & 7 & 7 & 7 \\ \end{matrix}

$\endgroup$
1
  • $\begingroup$ Thanks, especially dynamic programming part is very well done :) $\endgroup$
    – Oray
    Commented Jan 29, 2023 at 13:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.