算法 | 最长公共子序列
发布时间:2020-12-14 04:15:24 所属栏目:大数据 来源:网络整理
导读:? ? ? #includestdio.h#includestring.h#define MaxN 10000#define MaxC 10000int Val[MaxN][MaxN];double binaryKnapsack(int numItems,int *w,int *v,int capacity){ int i,j; for(i = 1; i = numItems; ++i) { for(j = 1; j = capacity; j++) { if(j w[i-
? ? ? #include<stdio.h> #include<string.h> #define MaxN 10000 #define MaxC 10000 int Val[MaxN][MaxN]; double binaryKnapsack(int numItems,int *w,int *v,int capacity) { int i,j; for(i = 1; i <= numItems; ++i) { for(j = 1; j <= capacity; j++) { if(j < w[i-1]) { Val[i][j] = Val[i-1][j]; continue; } if( (Val[i-1][j-w[i-1]] + v[i-1]) >Val[i-1][j]) { Val[i][j] = (Val[i-1][j-w[i-1]] + v[i-1]); } else { Val[i][j] = Val[i-1][j]; } } } /** for (i = 0; i < numItems; ++i) for (j = capacity; j >= 0; j--) if (j >= w[i] && Val[j] < Val[j - w[i]] + v[i]) Val[j] = Val[j - w[i]] + v[i]; return Val[capacity]; **/ return Val[numItems][capacity]; } int main() { int i,n,C,w[MaxN]; int v[MaxN]; int flag[MaxN]; int ans; while (scanf("%d%d",&C,&n) != EOF) { for (i = 0; i < n; ++i) scanf("%d",&w[i]); for (i = 0; i < n; ++i) scanf("%d",&v[i]); ans = binaryKnapsack(n,w,v,C); printf("%d",ans); int j = C; memset(flag,sizeof(flag)); for(int i = n; i > 0; i-- ) { if(Val[i][j] > Val[i-1][j]) { flag[i] = 1; j = j - w[i-1]; if(j < 0) break; } } for(int i = 1; i <= n; i++) { printf(" %d",flag[i]); } printf("n"); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |