Move bricks (greedy perturbation + 01 backpack)

The 13th National Blue Bridge Cup

Problem

Yes $n$ Items , The first $i$ The volume and value of each item are $v_i,w_i$ . Now from here n Take some items out of the items , Line up , Make the value of each item greater than or equal to the item in front of it Total volume . Find the maximum value of the items taken out .

Solution

Greedy perturbation is a little metaphysical .. You can do it first 《 King's game 》 The subject , Get to know “ Perturbation ” The process of analyzing a topic .

1. First , Considering how to ensure that the total volume of an item in front of it is less than the value of the item , There will be no clue . However , If it's difficult, it's the opposite .
   therefore , You can deal with the items in front first , Then deal with the following items first .

2. After that, choose items .
   After thinking, you can find , The selection order of items can affect the result , direct 01 The backpack seems inappropriate .（ I don't quite understand why sorting items will affect 01 It's a backpack dp The process , I hope some big guys can explain it in the comment area , thank [doge]）

3. How to sort ： Sort according to the sum of the value and volume of the goods from small to large .
   The proof method is ： Perturbation method .
   The following is the proof process

   1. Under the condition that the conditions in the topic are met ：
      Suppose... Of these items taken out $i$ Items and The first $i+1$ The volume and value of each item are ($v_i,w_i$)( $v_{i+1},w_{i+1}$)
      Set before $i-1$ The total volume of this article is $sum$

   2. According to the conditions in the title ： $$sum+v_i\le w_{i+1}$$

   3. In exchange for $i$ Items and $i+1$ Location of items ： Other items and article $i+1$ Items still meet the conditions in the title .( Simple thinking and analysis shows )

   4. And the first i Whether the item meets the conditions , There is a relationship ：
      If after the exchange $i$ Items Do not meet the conditions in the topic , Then the total value decreases , That is, the result becomes worse . So there are ：$$sum+v_{i+1}>w_i$$
      Two inequalities can be combined to obtain ：$$w_i-v_{i+1}<sum\le w_{i+1}-v_i$$
      namely $w_i-v_{i+1}<w_{i+1}-v_i$, It is reduced to ：$w_i+v_i<w_{i+1}+v_{i+1}$

   5. It can be seen from the above analysis ： When the first $i$ The sum of the value and volume of an article Less than The first $i+1$ The sum of the value and volume of an item , The result after exchange Variation .
      in other words ： If all the items were sorted from small to large according to the sum of value and volume ,
      After scrambling the order , There are more reverse pairs , The worse the result .

Code

#define ft first
#define sd second
#define pii pair<int, int>
const int N = 2e3 + 5;
pii s[N];
int f[20100];// Maximum volume ：20 + 20000

int main()
{
    
	IOS;
	int n; cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> s[i].ft >> s[i].sd;//first Is the volume ,second For value 
	sort(s + 1, s + n + 1, [&](pii &a, pii &b) {
    
		return a.ft + a.sd < b.ft + b.sd;
		});

	//dp[i][v]: front i Items , The total volume is v when , The maximum value that can be accommodated 
	// Select the first i Item , Before request i - 1 The total volume of this article is less than i The value of items 
	// Select the first i When it comes to items , Maximum volume  = s[i].ft + s[i].sd （ front i - 1 The total volume of the item plus i The volume of items v[i]）
	// Select the first i When it comes to items , Minimum volume  = s[i].ft （ There are no objects in front ,i Is the first item ）
	for (int i = 1; i <= n; i++)
		for (int v = s[i].ft + s[i].sd; v >= s[i].ft; v--)
			f[v] = max(f[v], f[v - s[i].ft] + s[i].sd);

	cout << *max_element(f, f + 20021) << endl;


	return 0;
}

Over