当前位置 博文首页 > ttoobne：POJ1742 Coins （可行性背包）
题目链接
题解：
看到面试题和这个很像，好像是挺经典的一个问题，定义一个 sum 数组代表第 i 枚硬币在达到硬币总数为?j 的时候使用了几枚，然后就可以控制硬币的使用次数了。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define PI acos(-1.0)
#define INF 0x3f3f3f3f3f3f3f3f
#define debug(x) cout << (#x) << ": " << (x) << " "
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define mod 998244353
const int M = 100000 + 10;
const int N = 100 + 10;
int n, m, a[N], c[N], sum[M], ans;
bool dp[M];
int main()
{
while(scanf("%d %d", &n, &m) && (n || m)) {
memset(dp, false, sizeof dp);
ans = 0;
for(int i = 1; i <= n; ++ i) {
scanf("%d", &a[i]);
}
for(int i = 1; i <= n; ++ i) {
scanf("%d", &c[i]);
}
dp[0] = true;
for(int i = 1; i <= n; ++ i) {
memset(sum, 0, sizeof sum);
for(int j = a[i]; j <= m; ++ j) {
if(!dp[j] && dp[j - a[i]] && sum[j - a[i]] < c[i]) {
ans ++;
dp[j] = true;
sum[j] = sum[j - a[i]] + 1;
}
}
}
printf("%d\n", ans);
}
return 0;
}
/*
Rejoicing in hope, patient in tribulation .
*/
面试题也没有题目链接不知道对不对，问的是从一个大小为 n 的数组里面能不能选出若干个数字使得总和为 k 的倍数。（数据范围：1 <= n <= 1e6, 1 <= k <= 2000）大概思路就是先把数组里的数字 mod 上 k 然后用可行性背包。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define PI acos(-1.0)
#define INF 0x3f3f3f3f3f3f3f3f
#define debug(x) cout << (#x) << ": " << (x) << " "
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define mod 998244353
const int M = 100000 + 10;
const int N = 100 + 10;
int n, k, num[N], sum[N];
bool dp[N];
int main()
{
scanf("%d %d", &n, &k);
for(int i = 1, a; i <= n; ++ i) {
scanf("%d", &a);
num[a % k] ++;
}
if(num[0]) {
printf("YES\n");
return 0;
}
dp[0] = true;
for(int i = 1; i < k; ++ i) {
memset(sum, 0, sizeof sum);
if(num[i] == 0) continue;
for(int j = i; j <= k; ++ j) {
if(!dp[j] && dp[j - i] && sum[j - i] < num[i]) {
dp[j] = true;
sum[j] = sum[j - i] + 1;
}
}
}
if(dp[k]) printf("YES\n");
else printf("NO\n");
return 0;
}
/*
Rejoicing in hope, patient in tribulation .
*/
?
cs