要求
有n种不同大小的数字
ai
,每种个
mi
个。判断是否可以从这些数字之中选出若干使他们的和恰好为K。
限制条件
(1 <= n <= 100)(1 <=
ai
,
mi
<= 100000)(1 <= K <= 100000)
输入格式
第一行输入n 接下来n行输入ai,mi 最后一行输入K
输出格式
如果有，则输出YES， 如果无，则输出NO
测试输入
3 3 3 5 2 8 2 17
测试输出
YES
解题思路
使用dp数组来存剩余数量个数，下标用来记录当前和。
代码
#include <iostream>
#include <cstring>
using namespace std;
int dp[
100001];
int main() {
int n;
cin >> n;
int a[
101],m[
101];
for (
int i =
0; i < n; i++) {
cin >> a[i] >> m[i];
}
int K;
cin >> K;
memset(dp, -
1,
sizeof(dp));
dp[
0] =
0;
for (
int i =
0; i < n; i++) {
for (
int j =
0; j <=K; j++) {
if (dp[j] >=
0) {
dp[j] = m[i];
}
else if (j < a[i] || dp[j - a[i]] <=
0) {
dp[j] = -
1;
}
else {
dp[j] = dp[j - a[i]] -
1;
}
}
}
if (dp[K] >=
0) {
cout <<
"YES" << endl;
}
else {
cout <<
"NO" << endl;
}
return 0;
}
