# nr CSI (3) CQI

2022-12-20   ES

Maximum Tape Utilization Ratio
1000(ms)
65535(kb)
917 / 3074
tags: greedy strategy

There are n programs {1,2, …, n} It is stored on a tape with length L. The length of the program I stored on the tape is li, 1 <= i <= n. The program storage problem requires a storage scheme of the n program on the tape so that the program that can store as many as possible on the tape. Under the premise of ensuring the most storage program, the tape’s utilization rate is required to reach the maximum. For the length of the given n program on the tape, the program number that can be stored on the tape can be calculated and occupied the length of the tape.

#### input

The first line is two positive integer, which represents the number of files n <= 600 and the length of the tape L <= 6000. In the next line, there are n positive integers, indicating the length of the program stored on the tape.

#### output

The number of programs that can be stored at most and the length of the tape can be stored in the first line of line; the length of each program stored on the tape 2 is the length of each program.

#### Sample input

```9 50
2 3 13 8 80 20 21 22 23
```

#### Sample output

```5 49
2 3 13 8 23```

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 ;
int Num ;
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 …………

source