A Writer’s Best Book
National Olympiad — Regional round (2013 season)
Submission name: book.cpp
Problem summary
Choose a subset of stories whose total page count is at most M, maximizing their total royalties. Each story may be included once.
Input
N M, followed by N pairs: page count and royalty in leva.
Output
The maximum royalty, with two decimal places.
Constraints
0<N,M<1000; each page count is between 1 and M; each royalty is positive, less than 100, and has exactly two decimal places.
Worked example
An independently prepared example for this explanation.
Input
5 8 2 10.20 3 13.42 1 15.12 4 21.23 2 9.45
Output
49.77
Solution analysis
- Convert money to integer cents. Maintain best[c], the greatest royalty obtainable using at most c pages from the stories processed so far.
- For a story of p pages and value v, update capacities in descending order: best[c]=max(best[c],best[c−p]+v). Descending order ensures the state best[c−p] still excludes the current story.
- In the sample, choose the stories with 3,1,4 pages: 13.42+15.12+21.23=49.77 within eight pages. The DP checks every subset implicitly.
Why it works
For each capacity, an optimal subset either excludes the new story, retaining the old value, or includes it, leaving capacity c−p for previous stories. The transition takes the better of these exhaustive cases, and descending updates prevent reuse.
Watch out. Use cents to avoid floating-point comparisons. Iterate capacities downward; an upward loop would solve the unbounded version.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int main(){
int count,capacity;
cin>>count>>capacity;
vector<int>best(capacity+1,0);
for(int i=0;i<count;i++){
int pages;
string money;
cin>>pages>>money;
size_t point=money.find('.');
int cents=stoi(money.substr(0,point))*100+stoi(money.substr(point+1));
// Descending capacity means this story is used at most once.
for(int c=capacity;c>=pages;c--){
best[c]=max(best[c],best[c-pages]+cents);
}
}
cout<<best[capacity]/100<<'.'<<setw(2)<<setfill('0')<<best[capacity]%100<<'\n';
}