It’s a bottom up approach.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <vector> #define INF 100000000 using namespace std; int MX; vector<int> vb[21]; int dp[201][21]; void init() { for(int i=0;i<21;i++) vb[i].clear(); MX = INF; for(int i=0;i<201;i++) for(int j=0;j<21;j++) { if(j==0) dp[i][j]=0; else dp[i][j]=-1;//not solved } } int _max(int a,int b) { if(a>b) return a; return b; } int main() { int t,K,a; int M,C; scanf("%d",&t); while(t--) { init(); scanf("%d%d",&M,&C); for(int i=1;i<=C;i++) { scanf("%d",&K); for(int j=0;j<K;j++) { scanf("%d",&a); vb[i].push_back(a); } }//for ends for(int i=1;i<=C;i++) { for(int j=0;j<vb[i].size();j++) { int val = vb[i][j]; for(int k=0;k<=M;k++) { if(val<=k && dp[k-val][i-1]!=-1) dp[k][i]=_max(dp[k-val][i-1]+val,dp[k][i]); } } } if(dp[M][C]==-1) printf("no solution\n"); else { printf("%d\n",dp[M][C]); } } return 0; } |