自己复习用 1.单调队列法 详见《挑战》p340 然后我其实不懂为什么在deq[s]==j-m[i]时去掉队首，过几天懂了我来更新，如果你知道的话请告诉我qq2298763866
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <vector> #include <algorithm> #include <queue> using namespace std; const int maxn=200; const int maxm=10100; const int maxw=10100; int n,wgh; int w[maxn]; int v[maxn]; int m[maxn]; int dp[maxn+maxm]; int main() { scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d%d%d",&w[i],&v[i],&m[i]); } scanf("%d",&wgh); int deq[maxn]; int deqv[maxn]; int s=0; int t=0; for(int i=0;i<n;i++) { for(int a=0;a<w[i];a++) { s=0; t=-1; for(int j=0;j*w[i]+a<=wgh;j++) { int b=dp[j*w[i]+a]-j*v[i];//加入单调队列的是b值 while(s<=t && deqv[t]<=b) { t--; } t++; deq[t]=j; deqv[t]=b; dp[j*w[i]+a]=deqv[s]+j*v[i]; // if(deq[s]==j-m[i]) { s++; } // } } } printf("%d\n",dp[wgh]); return 0; }2.二进制背包 9讲上有 不过自己写还是第一次
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <vector> #include <algorithm> #include <queue> using namespace std; const int maxn=200; const int maxm=10100; const int maxw=10100; int n,wgh; int w[maxn]; int v[maxn]; int m[maxn]; int dp[maxn+maxm]; int main() { scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d%d%d",&w[i],&v[i],&m[i]); } scanf("%d",&wgh); int num=0; for(int i=0;i<n;i++) { num=m[i]; for(int j=1;num>0;j<<=1) { int mul=min(j,num); for(int k=wgh;k>=w[i]*mul;k--) { dp[k]=max(dp[k],dp[k-w[i]*mul]+mul*v[i]); } num-=mul; } } printf("%d\n",dp[wgh]); return 0; }理由等我过几天懂了再来更
