Algorithim - creating a pattern

See more:

patterns

I would like to know if there is an algorithm that could help me solve the following example problem.

First off we have a list of 1 and 0:
011001010111 of length 12.

Then we have an x number of 1 to inject anywhere in the list, for instance x=3 (not necessary to inject all 3).

Lastly, we have a number y that checks the list for every y-th element for a 1.

For instance, y=4 which means the program in this example before injections will output 2 as 4th element contains a 0, but both 8th and 12th contain a 1.

The algorithm in this example should inject a maximum of three 1s into the list so that every 4th element would contain as few 1s as possible.

A correct answer for this example could look something like this:

(Injecting into list with first index being 1)

1. Injection at index 7 => list=0110011010111, length=13, output=1.
2. Injection at index 10 => list=01100110110111, length=14, output=1.
3. Injection at index 10 => list=011001101110111, length=15, output=0.

Another correct answer can also look like this:

1. Injection at index 1 => list=1011001010111, length=13, output=2.
2. Injection at index 1 => list=11011001010111, length=14, output=3.
3. Injection at index 1 => list=111011001010111, length=15, output=0.

Lenght=<10000, x=<50, y=<10000

What I have tried:

So far I have tried a simple approach that checks for the best injections for all injections, meaning that each time I inject, I inject at the best possible position that returns the least amount of 1. I was also told that this can be solved using dynamic programming with a matrix of x * (n/y). So if anyone can point me at the right direction or help me understand the implementation using the matrix would much appreciate it.