Hello friends,
I have a dynamic programming problem and would like to discuss it here.The problem goes as
Given an integer array A[0....i] convert it to an array of strictly increasing numbers.
The operations allowed are
1)Decrease an element by amount x: cost of operation=x
2)Delete an element k: cost of operation =k
And of course we have to find a solution with minimum cost .
scholar 0 Light Poster
Adak 419 Nearly a Posting Virtuoso
You can't delete an element from an array - they are fixed.
Why don't you post a simple example of what you want to do. Your description is dodgy, (or maybe it's just too early?). ;)
scholar 0 Light Poster
Thanks for reply.
Here is an example.
Suppose the given array is
1 3 2 8 4
We have to convert it to an array in such a way that all elements are in non decreasing order. An example would be
1 2 2 5 4
No that is possible in various manner. The cost for above transformation would be
0+1+0+3+0=4
We have to find the minimum cost for transformation.
Deleting an element here means that position in array will not be considered
Ex: 1 2 2 4
Cost here is 0+1+8+0=9 as we are deleting 8.
hope this makes it clear
Adak 419 Nearly a Posting Virtuoso
Note: non-decreasing == ascending order ;)
Fewest number of comparisons: Insertion sort.
Fewest number of swaps: Selection sort.
No comparisons at all: Counting sort (if the data is ranged OK for it)
So we're not trying to move the values (like using a sort), we're adjusting their values, and counting the cost incurred, until the numbers are in sorted order?
Hmmmmmm. . .
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.