9 50
2 3 13 8 80 20 21 22 23

5 49
2 3 13 8 23

Question link

First of all, when I went online to search for this question, there were only code and no solution. The most angry thing was that it was a code QWQ, so I wanted to write this blog and write a clear problem.

Second, this OJ’s tag is too water (greedy strategy) is not actually a dynamic plan.

Questions:

Thinking 1:

We open a structure with three information: the number of procedures, the length of the tape, all programs

dp[j].count    Represents the number of programs that can be stored at most in the length of the tape

dp[j].sumv    Represents the length of the tape that can be occupied by J for the length of the tape

dp[j].pre       represents the tape length occupied by each program that stores the Count program

First of all, we must meet the most storage program. If we are satisfied: dp [j] .count <DP [J -s] .count + 1, the data can be updated.

When the storage program is the same, we need to satisfy: dp [j] .sumv <= (dp [j -s] .sumv + s), that isThe number of programs is the same

In the case of, needThe largest tape occupation rate, if you meet the update data.

Then you can solve it, and the dynamic planning takes a wave: (Title pit point:Output minimum dictionary program program）

pit point test data:

5 8
2 4 4 6 8
ans is 
2 8
2 6(not 4 4)

Core code:

// Note the inverted order, 
 for (int i = n-1; i> = 0; i-) { 
 int s; 
 s = num [i]; 
 for (int j = m; j> = 0; j-) { 
 if (j -s> = 0) { 
 if (dp [j] .count <dp [j -s] .count + 1 || (dp [j] .count == (dp [j -s] .count + 1) 
 && dp [j] .sumv <= (dp [j -s] .sumv + s)) {// Note that it is equivalent to: when it is equal to directly overwriting, this is the largest dictionary order preface 
 dp [j] .count = dp [j -s] .count + 1; // But we used the backward narrative, so the in turn is the minimum dictionary order 
 dp [j] .pre = dp [j -s] .pre; 
 dp [j] .pre.push_back (s); 
 dp [j] .sumv = dp [j -s] .sumv + s; 
 } 
 } 
 } 
 }

Full code:

#include <iostream> 
 #include <string.h> 
 #include <algorithm> 
 #include <cmath> 
 #include <Map> 
 #include <string> 
 #include <stdio.h> 
 #include <vector> 
 #include <string> 
 #include <time.h> 
 #include <stack> 
 using namespace std; 
 #Define ll long long int 
 #Define Mod 1000000007 
 #Define Max (x, y) (x)> (y)? (x): (y) 
 using namespace std; 
 #Define Pi 3.14159265354 

 struct node { 
 int Sumv; 
 int count; 
 vector <LL> Pre; 
 node () {{{ 
 SUMV = 0; 
 count = 0; 
 pre.clear (); 
 } 
 }; 
 int Main () 
 {{ 
 iOS :: SYNC_WITH_STDIO (FALSE); 
 int n, m; 
 While (cin >> n >> m) { 
 node dp [6005]; 
 int Num [605]; 
 for (int i = 0; i <n; i ++) cin >> num [i]; 
 // Pay attention to the inverted order, 
 for (int i = n-1; i> = 0; i-) { 
 int s; 
 s = num [i]; 
 for (int j = m; j> = 0; j-) { 
 if (j -s> = 0) { 
 if (dp [j] .count <dp [j -s] .count + 1 || (dp [j] .count == (dp [j -s] .count + 1) 
 && dp [j] .sumv <= (dp [j -s] .sumv + s)) {// Note that it is equivalent to: when it is equal to directly overwriting, this is the largest dictionary order preface 
 dp [j] .count = dp [j -s] .count + 1; //, but we used the backward narrative, so the in turn is the minimum dictionary order 
 dp [j] .pre = dp [j -s] .pre; 
 dp [j] .pre.push_back (s); 
 dp [j] .sumv = dp [j -s] .sumv + s; 
 } 
 } 
 } 
 } 
 core << dp [m] .count << << dp [m] .sumv << Endl; 
 int len = dp [m] .pre.size (); 
 // Back narrative output 
 for (int i = len-1; i> = 0; i-) { 
 if (i! = Len-) COUT << ''; 
 core << dp [m] .pre [i]; 
 } 
 cout << Endl; 
 } 

 Return 0; 
 }

Thinking 2:

Since the data of this question is small, it can actually be solved with DFS:

first find the number of programs that can be stored at most, and then perform DFS to find the minimum dictionary order and the maximum tape utilization program. I look at the QWQ that someone has been like this in the background. It, QWQ you know …………