P1064 金明的預算方案

2019-11-10 19:36:03

字體：大中小

來源：轉載

供稿：網友

題見洛谷

由于依賴少，可以改為分組背包

#include<iostream>#include<cstdio>#include<cstring>#include<string> #include<algorithm>using namespace std;int v[210],c[210],n,m,wj[210][3],wpv[210],wpc[210]; int f[32000+10];bool p[210];int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int vv,pp,QQ; scanf("%d%d%d",&vv,&pp,&qq); v[i]=vv;c[i]=vv*pp; if(qq==0) p[i]=true; else wj[qq][++wj[qq][0]]=i,p[qq]=true;//wj[qq][++wj[！ qq ！][0]]=i } int cnt=0,x=1; for(int i=1;i<=m;i++) { if(p[i]) { wpv[++cnt]=v[wj[i][1]]+v[i],wpc[cnt]=c[wj[i][1]]+c[i]; wpv[++cnt]=v[wj[i][2]]+v[i],wpc[cnt]=c[wj[i][2]]+c[i]; wpv[++cnt]=v[wj[i][1]]+v[wj[i][2]]+v[i],wpc[cnt]=c[wj[i][1]]+c[wj[i][2]]+c[i]; wpv[++cnt]=v[i],wpc[cnt]=c[i]; } }//將依賴背包拆成分組背包 for(int i=1;i<=cnt;i=i+4) { for(int j=n;j>=0;j--) for(int k=0;k<=3;k++) if(j>=wpv[i+k]) f[j]=max(f[j],f[j-wpv[i+k]]+wpc[i+k]); }//注釋起的為第二種寫法/* for(int i=1;i<=m;i++) { if(p[i]) { for(int j=n;j>=0;j--) { int x1=v[i],x2=v[wj[i][1]]+v[i],x3=v[i]+v[wj[i][2]],x4=v[i]+v[wj[i][1]]+v[wj[i][2]]; if(j>=x1) f[j]=max(f[j],f[j-x1]+c[i]); if(j>=x2) f[j]=max(f[j],f[j-x2]+c[i]+c[wj[i][1]]); if(j>=x3) f[j]=max(f[j],f[j-x3]+c[i]+c[wj[i][2]]); if(j>=x4) f[j]=max(f[j],f[j-x4]+c[i]+c[wj[i][1]]+c[wj[i][2]]); } } }*/