Citus_Neru_index @ 2019-06-25 20:55:13
using namespace std; int n,m,v[65],p[65],q[65],a[65][4],opt[32005],arr[65]; int main() { int i,j,c; scanf("%d %d", &n,&m); for(i=1;i<=m;i++) { scanf("%d %d %d",&v[i],&p[i],&q[i]); arr[i]=v[i]p[i]; if(q[i]!=0) { a[q[i]][1]++; for(j=2;j<=4;j++) { if(a[q[i]][j]==0) {a[q[i]][j]=i;break;} } } } for(i=1;i<=m;i++) for(j=n;j>=1;j--) if(q[i]==0) { opt[j]=max(opt[j],opt[j-v[i]]+arr[i]); for(c=2;c<=(a[i][1]+1);c++) {opt[j]=max(opt[j],opt[j-v[a[i][c]]]+(v[a[i][c]]p[a[i][c]]));} } printf("%d ",opt[n]); return 0; }
本程序是想通过存储附件的信息到主件中，再坐在01中加一个循环，但是结果却是一个很大的数字，无奈本人能力有限，故求教各位大佬（救救孩子吧！）
by Citus_Neru_index @ 2019-06-25 20:56:01
#include<cstdio>
#include<iostream>
using namespace std;
int n,m,v[65],p[65],q[65],a[65][4],opt[32005],arr[65];
int main()
{
int i,j,c;
scanf("%d %d", &n,&m);
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&v[i],&p[i],&q[i]);
arr[i]=v[i]*p[i];
if(q[i]!=0)
{
a[q[i]][1]++;
for(j=2;j<=4;j++)
{
if(a[q[i]][j]==0)
{a[q[i]][j]=i;break;}
}
}
}
for(i=1;i<=m;i++)
for(j=n;j>=1;j--)
if(q[i]==0)
{
opt[j]=max(opt[j],opt[j-v[i]]+arr[i]);
for(c=2;c<=(a[i][1]+1);c++)
{opt[j]=max(opt[j],opt[j-v[a[i][c]]]+(v[a[i][c]]*p[a[i][c]]));}
}
printf("%d ",opt[n]);
return 0;
}by fzhfzh @ 2019-06-25 21:01:16
@Accelerator_zhang
本蒟蒻看不出错但可以提供代码
#include <iostream>
using namespace std;
int const N=32001,M=61;
int n,m,t,k,f[N],w[M][3],v[M],p[M],q[M],x[M];
int main(){
cin>>n>>m;//
for (int i=1;i<=m;i++){
cin>>v[i]>>p[i]>>q[i];
if (q[i]==0) x[++t]=i;//保存主件的物品序号
else w[q[i]][++w[q[i]][0]]=i;//保存附件, w[k][0]表示附件个数,w[k][1]表示附件1序号,w[k][2]表示附件2序号
}
for (int i=1;i<=t;i++) {//主件个数循环
k=x[i];//主件物品序号
for (int j=n;j>=0;j--){//总钱数
if (j>=v[k]) f[j]=max(f[j],f[j-v[k]]+v[k]*p[k]);//主件判断
if ((w[k][0]>=1) && (j>=(v[k]+v[w[k][1]])))//存在满足条件附件
f[j]=max(f[j],f[j-v[k]-v[w[k][1]]] + v[k]*p[k] + v[w[k][1]]*p[w[k][1]]);
if ((w[k][0]>=2) && (j>=(v[k]+v[w[k][2]])))
f[j]=max(f[j],f[j-v[k]-v[w[k][2]]]+v[k]*p[k]+v[w[k][2]]*p[w[k][2]]);
if ((w[k][0]>=2) && (j>=(v[k]+v[w[k][1]]+v[w[k][2]])))
f[j]=max(f[j],f[j-v[k]-v[w[k][1]]-v[w[k][2]]]+v[k]*p[k]+v[w[k][1]]*p[w[k][1]]+v[w[k][2]]*p[w[k][2]]);
}
}
cout<<f[n]<<endl;
return 0;
}by ferrum_cccp @ 2019-06-25 21:01:25
希望更丰富的展现？使用Markdown
by guoxinyugz @ 2019-06-25 21:07:11
这题想当年我也调了好久……再给一坨代码
#include<cstdio>
int n,m,v[66],p[66],q[66],f[66][32222]={0};
int a[66][66],b[66]={0},w[32222]={0};
int main()
{
scanf("%d%d",&n,&m);
n=n/10;
for(int i=1;i<=m;i++) b[i]=1;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&v[i],&p[i],&q[i]);
v[i]/=10;
p[i]*=v[i];
if(q[i]==0) a[i][1]=i;
else a[q[i]][++b[q[i]]]=i;
}
for(int i=1;i<=m;i++)
{
for(int j=2;j<=b[i];j++)
{
for(int k=n-v[a[i][1]];k>=v[a[i][j]];k--)
if(f[i][k-v[a[i][j]]]+p[a[i][j]]>f[i][k])
f[i][k]=f[i][k-v[a[i][j]]]+p[a[i][j]];
}
for(int j=n-v[a[i][1]];j>=0;j--)
{
f[i][j+v[a[i][1]]]=f[i][j]+p[a[i][1]];
}
for(int j=0;j<v[a[i][1]];j++) f[i][j]=0;
}
for(int i=1;i<=m;i++)
for(int j=n;j>=0;j--)
for(int k=1;k<=j;k++)
if(w[j]<w[j-k]+f[i][k]) w[j]=w[j-k]+f[i][k];
printf("%d",w[n]*10);
return 0;
}by zimindaada @ 2019-06-25 21:18:39
这道题有个坑，就是每行输出第三个数，表示主附件的，和属于第几个主件的，指的是第几行的东西
by zimindaada @ 2019-06-25 21:18:52
@zimindaada 可能是这个坑，我没仔细看
by _lcy_ @ 2019-06-25 21:21:57
我也调了好久，最终在题解的帮助下A了
给你一坨代码
#include<bits/stdc++.h>
using namespace std;
int N,M;
int zjw[200],zjp[200],fjw[200][10],fjp[200][10],f[32001];
int main(){
scanf("%d%d",&N,&M);
for(int i=1;i<=M;i++){
int v,p,q;
scanf("%d%d%d",&v,&p,&q);
if(q==0){
zjw[i]=v;
zjp[i]=v*p;
}
else{
fjw[q][0]++;
fjw[q][fjw[q][0]]=v;
fjp[q][fjw[q][0]]=v*p;
}
}
for(int i=1;i<=M;i++){
for(int j=N;zjw[i]!=0 && j>=zjw[i];j--){
f[j]=max(f[j],f[j-zjw[i]]+zjp[i]);
if(j>=zjw[i]+fjw[i][1])
f[j]=max(f[j],f[j-zjw[i]-fjw[i][1]]+zjp[i]+fjp[i][1]);
if(j>=zjw[i]+fjw[i][2])
f[j]=max(f[j],f[j-zjw[i]-fjw[i][2]]+zjp[i]+fjp[i][2]);
if(j>=zjw[i]+fjw[i][1]+fjw[i][2])
f[j]=max(f[j],f[j-zjw[i]-fjw[i][1]-fjw[i][2]]+zjp[i]+fjp[i][1]+fjp[i][2]);
}
}
printf("%d\n",f[N]);
return 0;
}by Citus_Neru_index @ 2019-06-27 20:56:45
谢谢各位了