P1858 多人背包

admin

https://www.luogu.org/problemnew/show/P1858

题目描述
求01背包前k优解的价值和

输入输出格式
输入格式：
第一行三个数K、V、N

接下来每行两个数，表示体积和价值

输出格式：
前k优解的价值和

输入输出样例
输入样例#1：
2 10 5
3 12
7 20
2 4
5 6
1 1
输出样例#1：
57
说明
对于100%的数据,K≤50,V≤5000,N≤200

universehyf

1. #include<iostream>
   
2. using namespace std;
   
3. #define FOR(i,n,m) for(int i=n;i<=m;i++)
   
4. #define For(i,n,m) for(int i=n;i>=m;i--)
   
5. int k,m,n,x,y,c,cc;
   
6. int v[5005],w[5005],t[52];
   
7. long long ans,f[5005][52];
   
8. int main()
   
9. {
   
10.     cin>>k>>n>>m;FOR(i,1,m) cin>>v[i]>>w[i];
    
11.     FOR(i,0,n+1) FOR(j,0,k+1) f[i][j]=-1;
    
12.     f[0][1]=0;FOR(i,1,m) For(j,n,v[i])
    
13.     {
    
14.         x=1;y=1;cc=0;
    
15.         FOR(h,1,k)
    
16.         {
    
17.             if(f[j][x]>=f[j-v[i]][y]+w[i]&&f[j][x]!=-1)
    
18.                 {t[h]=f[j][x++];cc++;}
    
19.             else if(f[j][x]<f[j-v[i]][y]+w[i]&&f[j-v[i]][y]!=-1)
    
20.                 {t[h]=f[j-v[i]][y++]+w[i];cc++;}
    
21.             else break;
    
22.         }
    
23.         FOR(h,1,cc) f[j][h]=t[h];
    
24.     }
    
25.     FOR(i,1,k)
    
26.     {
    
27.         if(f[n][i]==-1) break;
    
28.         ans+=f[n][i];
    
29.     }
    
30.     cout<<ans;
    
31.     return 0;
    
32. }

复制代码

universehyf

1. #include<iostream>
   
2. using namespace std;
   
3. #define FOR(i,n,m) for(int i=n;i<=m;i++)
   
4. #define For(i,n,m) for(int i=n;i>=m;i--)
   
5. int k,m,n,x,y,c,cc;
   
6. int v[5005],w[5005],t[52];
   
7. long long ans,f[5005][52];
   
8. int main()
   
9. {
   
10.     cin>>k>>n>>m;FOR(i,1,m) cin>>v[i]>>w[i];
    
11.     FOR(i,0,n+1) FOR(j,0,k+1) f[i][j]=-1;
    
12.     f[0][1]=0;FOR(i,1,m) For(j,n,v[i])
    
13.     {
    
14.         x=1;y=1;cc=0;
    
15.         FOR(h,1,k)
    
16.         {
    
17.             if(f[j][x]>=f[j-v[i]][y]+w[i]&&f[j][x]!=-1)
    
18.                 {t[h]=f[j][x++];cc++;}
    
19.             else if(f[j][x]<f[j-v[i]][y]+w[i]&&f[j-v[i]][y]!=-1)
    
20.                 {t[h]=f[j-v[i]][y++]+w[i];cc++;}
    
21.             else break;
    
22.         }
    
23.         FOR(h,1,cc) f[j][h]=t[h];
    
24.     }
    
25.     FOR(i,1,k)
    
26.     {
    
27.         if(f[n][i]==-1) break;
    
28.         ans+=f[n][i];
    
29.     }
    
30.     cout<<ans;
    
31.     return 0;
    
32. }

复制代码