This problem looks like knapsack with repetition but limits are huge and I can't find a solution using DP, Could anyone tell me how to solve it, here is the link. http://poj.org/problem?id=3900
I have seen this kind of problems several times but I have never been able to solve them. Thanks in advance....
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 163 |
| 2 | adamant | 150 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 144 |
| 5 | errorgorn | 141 |
| 6 | cry | 139 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
N is not too big, so you can test all subsets of a given set. For each subset you can calculate its weight and cost in linear time. It's a O(N·2N) per test solution, and it seems to be OK.
UPD: that's not a solution, I didn't get the problem corerctly.
Inside the box with number k there are k very big diamonds, each of weight Wk and cost Ck.
But how if each element can be taken several times...
Sorry, I misread the statement and was wrong. So, in the correct problem N is less or equal then 120.
I don't think that there exists a polynomial solution. Maybe meet in the middle or something, but I can't see get it right now. Anyway, maybe bactracking with good pruning and greedy optimisations, simulated annealing or other heuristics like these can get AC (but not solve the problem).
120? Correct problem? Please explain this moment, i don't get it.
Meet-in-the-middle is simple, but too slow. we can divide diamonds into two groups 1..10 and 11..15, for each of the groups brute-force answers, then sort two arrays of pairs (weight, cost). now we can find in linear time (using two's pointers method) two elements with total weight less than or equal to M and with maximal cost.
I meen there are 120 possible diamonds. (1 from first box, 2 from second etc). I know. That's why I didn't find a solution yet :) How do you want to brute-force answers for each group? They are large enough, too. Or you mean backtracking with heuristics?
there is only 11! answers for first group and 12 * 13 * 14 * 15 * 16 for second.
You're right again! I have an exam tomorrow, and my head is going to blow up. I can't see obvious things. I'd better postpone thinking about problems until tomorrow evening.
Excuse me, I tried to write solution using your idea, but this code gets ML and I cannot figure out why!
Can anyone explain my trouble?
Maximum size of vector must be about 10! ≈ 3·106.
Sorry for my poor english...
Because it's wrong solution. As i said it is too slow (and uses too many memory). Memory limit is 65536K one of yours vectors uses 12 * 3 * 10^6 bytes (in the ideal test case, vector can use twice more memory than it have to use, because of it's implementation) you can try to reserve memory a[0].reserve(10!). But it will be TL.
Oh...I forgot that we have 16! answers (not 15!) and maximum size is 4586400 = 3·5·7·13·14·15·16.
I should read comments carefully...
Anyway, thanks for your advice!
I don't know for sure, and i can't prove this, but it seems to be true: we must to find solution for the case when we steal something that can be divided as we want (for example different types of the sand) solve problem for this case (it's easy, we must to take the most expensive sand as many as we can). Now solutions for this problem differs only by +/-1 for each type. Let we have solution S for "sand problem". S[i] means how many sand of type I must be taken. We want to know real solution R, i think R[i] is equal to Floor(S[i]) or Ceil(S[i]). Floor(X) is the nearest integer less than or equal to X, Ceil(X) is the nearest integer greater than or equal to X.
I must be wrong, it' seems like there must be O(2^n*poly) or O(3^n)
In the opposite case N can be bigger. Also, there will be only one element of S with realy REAL value.
And what about this solution? We look through subsets. If current box is in the subset, then R[i] = floor(S[i]), otherwise R[i] = ceil(S[i]). This is correct if your suggestion about +/-1 is correct.
Oh, I didn't see your previous post. Only one of S[i] is real, so probably it's not correct. Keep thinking.
I thought about that, when think about this solution, but then I have realized that there is only one real REAL value :)
Nice, we have only two possible masks :D
So, maybe we have to look through all subsets, Let's keep thinking in this direction... Maybe there is another S, which have this property?
This problem seems hard,but actually just simply search with some insightful pruning ( and reorder the items by some greedy idea) can succeed.
Please, share your idea. I can't solve it.