Problem link: http://lightoj.com:81/volume/problem/1233
My solution:
#include <bits/stdc++.h>
#define mx 100005
using namespace std;
vector<int> dp[105];
int a[105];
int c[105];
bool mark[mx];
int n, m;
void coin_change(int i, int sum){
mark[sum] = true;
if(sum == m || i == n || dp[i][sum] != -1){
return;
}
int j;
for(j = 0; j <= c[i] and sum + j * a[i] <= m; j++){
coin_change(i + 1, sum + j * a[i]);
dp[i + 1][sum + j * a[i]] = 1;
//mark[sum + j * a[i]] = true;
}
}
int main(){
//freopen("in.txt", "r", stdin);
int t, tc, i, cnt, j;
scanf("%d", &tc);
for(t = 1; t <= tc; t++){
scanf("%d %d", &n, &m);
for(i = 0; i < n; i++){
scanf("%d", &a[i]);
}
for(i = 0; i < n; i++){
scanf("%d", &c[i]);
}
for(i = 0; i <= n; i++){
for(j = 0; j <= m; j++){
dp[i].push_back(-1);
}
}
memset(mark, false, sizeof mark);
coin_change(0, 0);
cnt = 0;
for(i = 1; i <= m; i++){
if(mark[i]) cnt++;
}
printf("Case %d: %d\n", t, cnt);
for(i = 0; i <= n; i++){
dp[i].clear();
}
}
return 0;
}
Basic solution is DP[i][j] = can we make value j by using up to ith coin?. DP[i][j] is true if some of the values DP[i - 1][j - k * A[i]] is true, with k ≤ C[i]. Note that instead of using two dimensions for our DP, we can use only one and process the values in reverse order (from M down to 0). To process coin i, we sit at value j and, if it's true, we also set to true all values j + k * A[i] with k ≤ C[i].
However, this solution without any optimization gets TLE. One simple pruning we can make which is enough to get Accepted is to have an auxiliary array Last[j] that stores what coin we used the last time we saw j. If we're ever trying to update value j and we see that Last[j] = i, we can safely stop there, since it doesn't make any sense to update all values j + k * A[i] if we already updated all values j + A[i] + k * A[i] previously.
Your solution is really straightforward, simple and beautiful. It helped a lot.
Thanks :)