有 n 瓶水,第 ii 瓶水的水量为 ai,容量为 bi。
将 1 单位水从一个瓶子转移到另一个瓶子所消耗时间为 1秒,且可以进行无限次转移。
求储存所有水所需最小瓶子数 k 以及该情况下所用最小时间 t。
第一问直接贪心
第二问 dp
f[i ][j ][k] k为已经选的装水的瓶子数,J为水的体积
#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 102, M=1e4+2; const int inf =0x3f3f3f3f; struct T{ int a,b; }arr[N] ; int n,SA,SB,cnt,f[M][N]; bool cmp(T &x,T &y){ return x.b>y.b; } signed main(){ int i,j; cin>>n ; for(int i=1;i<=n;i++){cin>>arr[i].a; SA+=arr[i].a;} for(int i=1;i<=n;i++) cin>>arr[i].b; sort(arr+1,arr+n+1,cmp); while(SB<SA) SB+=arr[++cnt].b; cout<<cnt<<' '; memset(f,-127,sizeof(f)); f[0][0]=0; for(i=1;i<=n;i++) for(j=SB;j>=arr[i].b;j--) for(int k=1;k<=cnt;k++){ f[j][k]=max(f[j][k],f[j-arr[i].b][k-1]+arr[i].a); } int ans=0; for(int i=SA;i<=SB;i++) ans=max(ans,f[i][cnt]); cout<<SA-ans; }