华师一附中OI组

标题: P1858 多人背包 [打印本页]
作者: admin    时间: 2018-9-28 16:52
标题: P1858 多人背包
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    时间: 2018-10-19 22:28
  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    时间: 2018-10-21 20:49
  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. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2