こちらではpaiza事務局側で作成した模範解答を掲載していす。
C++: paiza事務局作成コード Vol.2 動的計画法
得点：100点
通過テストケース：7/7
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
int main() {
int M, N; cin >> M >> N;
vector<int> qs(M), rs(N);
int sumq = 0, sumr = 0;
for(int i = 0; i < N; i++) {
cin >> qs[i] >> rs[i];
sumq += qs[i];
sumr += rs[i];
}
int m = sumq - M;
vector<int> dp(m + 1, 0);
for(int i = 0; i < N; i++) {
int q = qs[i], r = rs[i];
for (int j = m; j >= q; j--) dp[j] = max(dp[j], dp[j - q] + r);
}
cout << sumr - dp[m] << endl;
return 0;
}
C++: paiza事務局作成コード Vol.1 O(2^n)
得点：71点
通過テストケース：5/7
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main() {
int M, N; cin >> M >> N;
vector<int> qs(N), rs(N);
for(int i = 0; i < N; i++) {
cin >> qs[i] >> rs[i];
}
//m社のうちi番目の会社を使うか使わないかの表を作る
//3社とかなら
// A, B, C
// 1, 1, 1
// 1, 1, 0
// 1, 0, 1
//.....続く...
//みたいな1を使う0は使わないの表を作る
vector< vector<int> > use_list (pow(2,N), vector<int>(N) );
for (int i = 0; i < (1<< N); i++) {
for (int j = 0; j < N; j++) {
use_list[i][j] = (i>>j&1);
}
}
//使う使わないリストから、人月を満たせる組み合わせで最安を探す
int ans = 0;
for (int i = 0; i < N; i++){
ans += rs[i];
}
int ningetsu = 0;
int cost = 0;
for (int i = 0; i < (1<<N); i++){
cost = 0;
ningetsu = 0;
for (int j = 0; j < N; j++){
if (use_list[i][j] == 1){
ningetsu += qs[j];
cost += rs[j];
}
}
if (ningetsu >= M && ans > cost){
ans = cost;
}
}
cout << ans << endl;
}
