Luogu-P1776 Treasure Screening

Original link: https://blog.chungzh.cn/articles/luogu-p1776/

Luogu-P1776 Treasure Screening

meaning of the title

Finally, the thousand-year-old problem has been solved. Little FF found the treasure room of the royal family, which was filled with countless valuable treasures.

This little FF can make a fortune, quack. But there are too many treasures here, and the collection car of the little FF seems to be unable to hold so many treasures. It seems that the little FF can only give up some of the treasures with tears.

Little FF sorted out the treasures in the cave, and found that each treasure has one or more pieces. He roughly estimated the value of each treasure, and then started the treasure screening work: Little FF has a collection vehicle with a maximum load of $W$, and there are a total of $n$ kinds of treasures in the cave, and the value of each treasure is $v_i $, the weight is $w_i$, and there are $m_i$ pieces of each treasure. Little FF hopes to select some treasures and put them into the collection vehicle to maximize their value on the premise that the collection vehicle is not overloaded.

For $100%$ of data, $n\leq \sum m_i \leq 10^5$, $0\le W\leq 4\times 10^4$, $1\leq n\le 100$.

Solution 1: Binary Optimization

Every number can be represented as a sum of powers of $2$ (because every number can be represented in binary).

Time complexity: $O(nW\sum \log m_i)$

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 

 #include <bits/stdc++.h> using namespace std ; int dp [ 40005 ]; int main () { int n , W ; scanf ( "%d%d" , & n , & W ); for ( int i = 0 ; i < n ; i ++ ) { int t , c , p ; scanf ( "%d%d%d" , & c , & t , & p ); int tmp = 1 ; while ( p >= tmp ) { p -= tmp ; for ( int j = W ; j >= t * tmp ; j -- ) dp [ j ] = max ( dp [ j ], dp [ j - t * tmp ] + c * tmp ); tmp *= 2 ; } if ( p == 0 ) continue ; for ( int j = W ; j >= t * p ; j -- ) { dp [ j ] = max ( dp [ j ], dp [ j - t * p ] + c * p ); } } printf ( "%d \n " , dp [ W ]); return 0 ; }

Solution 2: Monotonic queue optimization

Let $f[i][j]$ denote the maximum value of the first $i$ items whose weight does not exceed $j$. Obviously there is a state transition equation:

$$
f[i][j] = max_{0<=k<=m[i]}{f[i-1][jk\times w[i]]+k\times v[i]}
$$

We set $j=k_1*w[i]+d$:

$$
f[i][j]=max{f[i-1][(k_1-k)\times w[i]+d]-(k_1-k)\times v[i] }+ k_1\times v[ i]
$$

By enumerating the remainders $d$ and $k_1$, we can represent each number, and then maintain a monotonic queue. The decisions in this queue can be made into $j$ by adding the $i$ item, so increase The number cannot exceed $m[i]$, that is, $k_1-k <= m[i]$.

Time complexity: $O(nW)$

RECORD

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 

 #include <bits/stdc++.h> using namespace std ; int n , W ; int v [ 105 ], w [ 105 ], m [ 105 ]; int dp [ 105 ][ 40004 ]; struct deq { int head , tail ; int arr [ 40004 ]; bool empty () { return head + 1 == tail ; } void pop_front () { head ++ ; } void pop_back () { tail -- ; } void push_back ( int x ) { arr [ tail ] = x ; tail ++ ; } void clear () { head = 0 ; tail = 1 ; } int front () { return arr [ head + 1 ]; } int back () { return arr [ tail - 1 ]; } } dq ; int main () { cin >> n >> W ; int ans = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { cin >> v [ i ] >> w [ i ] >> m [ i ]; if ( w [ i ] == 0 ) { ans += v [ i ] * m [ i ]; continue ; } for ( int j = 0 ; j < w [ i ]; j ++ ) { // 余数dq . clear (); // k 实际上表示的是文中的k_1 for ( int k = 0 ; j + k * w [ i ] <= W ; k ++ ) { // dq.front() 实际上表示的是文中的k_1 - k while ( ! dq . empty () && k - dq . front () > m [ i ]) dq . pop_front (); while ( ! dq . empty () && dp [ i - 1 ][ j + dq . back () * w [ i ]] + ( k - dq . back ()) * v [ i ] <= dp [ i - 1 ][ j + k * w [ i ]]) dq . pop_back (); dq . push_back ( k ); if ( ! dq . empty ()) dp [ i ][ j + k * w [ i ]] = max ( dp [ i ][ j + k * w [ i ]], dp [ i - 1 ][ j + dq . front () * w [ i ]] + ( k - dq . front ()) * v [ i ]); } } } cout << dp [ n ][ W ] + ans << endl ; return 0 ; }

This article is reproduced from: https://blog.chungzh.cn/articles/luogu-p1776/
This site is for inclusion only, and the copyright belongs to the original author.