Geek asks and answers

The algorithm for buying maximum elements

We have N gold coins and silver coins. There are k items, each of which has a certain value, gold coins and silver coins B, where A or B can also be equal to zero.

What could be an algorithm to buy the maximum number of items?

+3
source share
3 answers

In this task, each item has a two-dimensional value. Let element i have value c [i] = <a, b> where a is the value of gold coins and b is the value of silver coins.

Now the elements can be partially ordered so that the element i is “no more expensive” than the element j if

c[i] = <a, b>    c[j] = <a', b'>  and    a <= a' AND b <= b'

, . < 1, 2 > < 2, 1 > ; , .

, , " " , , (, ) .

,

 <1, 1>
 <2, 1>
 <1, 2>
 <3, 3>

:

        <1, 1>
       /      \
     <2, 1>   <1, 2>
         \   /
         <3, 3>

( ). < 1, 1 > . < 2, 1 > < 1, 2 > . < 2, 1 > , < 1, 2 > , , (< 3, 3 > ).

. < 2, 1 > , < 1, 2 > , < 3, 0 > = 4, = 2, < 1, 2 > <, 3, 0 > , < 2, 1 > , ( < 2, 1 > , ).

, . , .

+4

?

, , Knapsack. , . Knapsack . , . , , , !

:

  • -
  • - .

, N M, , :

1. Sort the items by cost, from cheapest to the most expensive.
2. totalCost = 0; i = 1
3. while totalCost <= goldToCost(N) + silverToCost(M) + item[i].cost
4.    totalCost = totalCost + items[i].cost
5.    i++
6. endWhile
7. return i

O (nlogn) - .

, . , . .

. , :

  • . ? , S(M, N) , , M N . S(M, N) ?
  • . S (M, N), , ?

N M.

+---+---+---+---+---+-----+---+
|   | 0 | 1 | 2 | 3 | ... | N |
+---+---+---+---+---+-----+---+
| 0 |   |   |   |   |     |   |
| 1 |   |   |   |   |     |   |
| 2 |   |   |   |   | ... |   |
| 3 |   |   |   |   |     |   |
| : |   |   |   |   |     |   |
| M |   |   |   |   |     |   |
+---+---+---+---+---+-----+---+

. i, j S[i, j] , j .

, , i D. , - . , , . 0- . ,

S[0, 0] = 0
S[i, j] = 0   if i < 0 or j < 0 
S[i, j] = max(S[i-1,j-1] + d[i-1,j-1], S[i-1,j] + d[i-1,j], S[i,j-1] + d[i,j-1])

d[i*,j*] - , , <i,j> - <i*, j*>, <i*, j*> {<i-1, j-1>, <i-1, j>, <i, j-1>}. , , . (i D).

O ((MN + n) logn) O (MN + n) .

+4

"".

- NP- . SMALL- , N, M k, . "" , , .

Closest to solving this is a field known as linear programming. This ... is not a simple thing, but you can read it if you want.

-2
source

More articles:


All Articles