~~~ void dp2(int *w, int *v, int n, int c){cout<<"dp2:"<<endl; int vs = 0; for(int i=0;i<n;i++) vs += v[i]; int **m; m = new int*[n+1]; for (int i = 0; i<n + 1; i++) { m[i] = new int[vs+1]; for (int j = 0; j<vs + 1; j++) m[i][j]=-1;//2147483647 } for(int i=0;i<n+1;i++) m[i][0] = 0; m[1][v[0]] = w[0]; for(int i=2;i<=n;i++){ for(int j=1;j<=vs;j++){ if(j<v[i-1]) m[i][j] = m[i-1][j]; else{ int a = m[i-1][j]; int b = m[i-1][j-v[i-1]]; if(b==-1){ m[i][j] = a; } else{ b += w[i-1]; if(a==-1||b<a) m[i][j] = b; else m[i][j] = a; } } } } // for (int i = 0; i <= n; i++) { // for (int j = 0; j <= vs; j++) cout << m[i][j] << "\t"; // cout << endl; // } int *x; x = new int[n+1]; int maxV=0; for(int i=vs;i>0;i--){ if(m[n][i]<=c&&m[n][i]!=-1){ maxV = i; break; } } for(int i=n;i>0;i--){ if(m[i][maxV]==m[i-1][maxV]) x[i] = 0; else { x[i] = 1; maxV -= v[i-1]; } } // for (int i = 1; i <= n; i++) cout << x[i] << "\t"; cout << endl; } void adp(int *w, int *v, int n, int c,int e){cout<<"adp:"<<endl; int k = n/e; int vmax = 0; for(int i=0;i<n;i++) if(vmax<v[i]) vmax=v[i]; for(int i=0;i<n;i++) v[i] = v[i]*k/vmax; dp2(w, v, n, c); } ~~~