思路:多重背包+完全背包,完全背包用于找零因此从大到小背包
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <cmath> #define CL(a,b) memset(a,b,sizeof(a)) #define MIN(a,b) (a<b?a:b) #define INF 0x7ffffff using namespace std; const int M(10010); const int N(110); int c[N],v[N],f[M],n,t; void solve() { int i,j,k,l; for(i=0;i<M;i++) f[i]=INF; f[0]=0; for(i=0;i<n;i++) { j=1; int num; l=c[i]; while(j<l) { num=j*v[i]; for(k=M-1;k>=num;k--) f[k]=MIN(f[k],f[k-num]+j); l-=j; j<<=1; } num=l*v[i]; for(k=M-1;k>=num;k--) f[k]=MIN(f[k],f[k-num]+l); } for(i=0;i<n;i++) for(k=M-1-v[i];k>=0;k--) f[k]=MIN(f[k],f[k+v[i]]+1); if(f[t]!=INF) printf("%d\n",f[t]); else printf("-1\n"); } int main() { int i; while(scanf("%d%d",&n,&t)!=EOF) { for(i=0;i<n;i++) scanf("%d",&v[i]); for(i=0;i<n;i++) scanf("%d",&c[i]); solve(); } return 0; }