呵呵。。。超时了啊，不懂啊
先看看人家的正确代码，很长，思路感觉有点复杂
#include<iostream> #include<cstdio> #include<cstring> #define inf 0x7fffffff #define min(x,y) x<y?x:y using namespace std; int b[7]={1,6,36,216,1296,7776,46656}; struct good { int code,num,price; }basket[5]; struct sta { int state; int price; }offer[100]; int n,num,state; int flag[1000]; int dp[46656]; bool cheack(int p1,int p2)//两个状态能否相加的合法性判断 { int i; for(i=0;i<n;i++) { if((p1%6+p2%6)>basket[i].num) return false; p1/=6; p2/=6; } return true; } int cal(int p)//状态产生价值计算 { int i; int sum=0; for(i=0;i<n;i++) { sum+=(p%6)*basket[i].price; p/=6; } return sum; } int main() { int i,j,k,ans,num; while(scanf("%d",&n)!=EOF) { state=0; for(i=0;i<1000;i++) flag[i]=6; memset(basket,0,sizeof(basket)); for(i=0;i<n;i++) { scanf("%d%d%d",&basket[i].code,&basket[i].num,&basket[i].price); flag[basket[i].code]=i; state+=basket[i].num*b[i];//状态的产生 } scanf("%d",&num); int goodnum,temp,tempco; memset(offer,0,sizeof(offer)); for(i=0;i<num;i++) { scanf("%d",&goodnum); for(j=0;j<goodnum;j++) { scanf("%d%d",&tempco,&temp); offer[i].state+=b[flag[tempco]]*temp;//单个状态的产生 } scanf("%d",&offer[i].price); } for(i=0;i<=state;i++) dp[i]=inf; dp[0]=0; for(i=0;i<num;i++) for(j=0;j<=state;j++) { if(dp[j]==inf) continue; if(j+offer[i].state<=state&&cheack(j,offer[i].state))//最优值选择 dp[j+offer[i].state]=min(dp[j]+offer[i].price,dp[j+offer[i].state]); } ans=inf; for(i=0;i<=state;i++)//最后产生结果的处理 { if(dp[i]==inf) continue; ans=min(dp[i]+cal(state-i),ans); } printf("%d ",ans); } return 0; }
我的代码，坑爹的类似多重背包问题啊，循环可能多了一些，所以超时了，不过我看网上其他跟我一样思路的娃的代码，他们是runtime error ，我的是超时了，所以我有点怀疑这样的思路对与否了
#include "iostream" #include "string.h" #include "algorithm" using namespace std; struct{ int num,p; }w[2000][1000]; int h[100000]; int main(){ int e,top,i,c,k,p,b[6],s,ans,a,j,l,m,dp[6][6][6][6][6],v[10]; cin>>e; top=1; memset(b,0,sizeof(b)); memset(v,0,sizeof(v)); for(i=1;i<=e;i++){ cin>>c>>k>>p; v[c]=k; w[top][c].num=1; h[top++]=p; b[i]=c; } cin>>s; for(i=1;i<=s;i++){ cin>>ans; for(j=1;j<=ans;j++){ cin>>c>>k; w[top][c].num=k; } cin>>p; h[top]=p; top++; } memset(dp,127,sizeof(dp)); dp[0][0][0][0][0]=0; int a1=v[b[1]],a2=v[b[2]],a3=v[b[3]],a4=v[b[4]],a5=v[b[5]]; for(a=1;a<top;a++){ for(i=0;i<=a1;i++){ for(j=0;j<=a2;j++){ for(k=0;k<=a3;k++){ for(l=0;l<=a4;l++){ for(m=0;m<=a5;m++){ if(i-w[a][b[1]].num>=0&&j-w[a][b[2]].num>=0&&k-w[a][b[3]].num>=0&&l-w[a][b[4]].num>=0&&m-w[a][b[5]].num>=0) if(dp[i][j][k][l][m]>dp[i-w[a][b[1]].num][j-w[a][b[2]].num][k-w[a][b[3]].num][l-w[a][b[4]].num][m-w[a][b[5]].num]+h[a]){ dp[i][j][k][l][m]=dp[i-w[a][b[1]].num][j-w[a][b[2]].num][k-w[a][b[3]].num][l-w[a][b[4]].num][m-w[a][b[5]].num]+h[a]; } } } } } } } cout<<dp[a1][a2][a3][a4][a5]<<endl; }