hdu3449 有依赖的背包问题
发布时间:2020-12-14 05:24:46 所属栏目:百科 来源:网络整理
导读:不解释了,我估计难讲清楚,看代码吧。 #includeiostream#includecstdio#includealgorithm#includecmath#includecstringusing namespace std;int f[100005],d[100005];int main(){ int n,ww; while(scanf("%d%d",n,ww)!=EOF){ int i,j,k,v[101],mi[101],c[10
不解释了,我估计难讲清楚,看代码吧。 #include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; int f[100005],d[100005]; int main() { int n,ww; while(scanf("%d%d",&n,&ww)!=EOF){ int i,j,k,v[101],mi[101],c[101][25],w[101][25]; memset(f,sizeof(f)); memset(d,sizeof(d)); for(i=1;i<=n;i++){ scanf("%d%d",&v[i],&mi[i]); for(j=1;j<=mi[i];j++){ scanf("%d%d",&c[i][j],&w[i][j]); } } for(i=1;i<=n;i++){ for(k=0;k<=ww-v[i];k++) f[k+v[i]]=d[k]; for(k=1;k<=mi[i];k++) for(j=ww;j>=v[i]+c[i][k];j--){ f[j]=max(f[j],f[j-c[i][k]]+w[i][k]); } for(k=v[i];k<=ww;k++) d[k]=max(f[k],d[k]); } printf("%dn",d[ww]); } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
相关内容