考察:多重背包dp
思路:
多重背包板子,然后注意压掉一重循环需要倒序体积....
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 using namespace std;
5 typedef long long LL;
6 const int N = 626,M = 2010;
7 int n,k[N],c[N];
8 LL m,sum,f[M*N];
9 int main()
10 {
11 scanf("%d%lld",&n,&m);
12 for(int i=1;i<=n;i++) scanf("%d",&k[i]);
13 for(int i=1;i<=n;i++) scanf("%d",&c[i]),sum+=k[i]*c[i];
14 if(!m) {puts("0"); return 0;}
15 f[0] = 1;
16 for(int i=1;i<=n;i++)
17 for(int j=sum;j>=0;j--)
18 for(int s=1;s<=k[i]&&s*c[i]<=j;s++)
19 f[j] = max(f[j-s*c[i]]*s,f[j]);
20 for(int i=1;i<=sum;i++)
21 if(f[i]>=m) {printf("%d\n",i); return 0;}
22 return 0;
23 }