本文主要是介绍codeforces 730J - Bottles，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Nick has n bottles of soda left after his birthday. Each bottle is described by two values: remaining amount of soda ai and bottle volume bi (ai ≤ bi).Nick has decided to pour all remaining soda into minimal number of bottles, moreover he has to do it as soon as possible. Nick spends x seconds to pour x units of soda from one bottle to another.
Nick asks you to help him to determine k — the minimal number of bottles to store all remaining soda and t — the minimal time to pour soda into k bottles. A bottle can't store more soda than its volume. All remaining soda should be saved.
Input
The first line contains positive integer n (1 ≤ n ≤ 100) — the number of bottles.
The second line contains n positive integers a1, a2, ..., an (1 ≤ ai ≤ 100), where ai is the amount of soda remaining in the i-th bottle.
The third line contains n positive integers b1, b2, ..., bn (1 ≤ bi ≤ 100), where bi is the volume of the i-th bottle.
It is guaranteed that ai ≤ bi for any i.
Output
The only line should contain two integers k and t, where k is the minimal number of bottles that can store all the soda and t is the minimal time to pour the soda into k bottles.
这一题先是计算出所需瓶子的数量，然后就是0-1背包套进去
我原以为三维的三个循环要超时掉，网上有有用两个循环的。
dp[i][k][j]表示前i个取k个恰好b的总和为j时a的总和的最大值。
第i个不屈，dp[i][k][j]=dp[i-1][k][j]
第i个取，dp[i][k][j]=max(dp[i][k][j], dp[i-1][k-1][j-b[i]]+a[i]);
AC代码：
# include <stdio.h>
# include <string.h>
# include <algorithm>
using namespace std;
const int inf=2000000000;
int dp[2][110][10010],sum[110], a[110], b[110], t_b[110];//前n项和
bool cmp(int a, int b){return a>b;
}
int main(){int i, j, k, n, l_sum=0, temp, K;scanf("%d", &n);for(i=1; i<=n; i++){scanf("%d", &a[i]);l_sum=a[i]+l_sum;}for(i=1; i<=n; i++){scanf("%d", &b[i]);t_b[i]=b[i];sum[i]=b[i]+sum[i-1];}sort(b+1, b+n+1, cmp);temp=0;for(K=1; K<=n; K++){temp=temp+b[K];if(temp>=l_sum){break;}}for(int i=0; i<2; i++){for(int k=0; k<=K; k++){for(int j=0; j<=sum[n]; j++){dp[i][k][j]=-inf;}}}int t=0;dp[0][0][0]=dp[1][0][0]=0;for(i=1; i<=n; i++, t=t^1){for(j=0; j<=sum[i]; j++){for(k=1; k<=i&&k<=K; k++){dp[t][k][j]=dp[t^1][k][j];if(j>=t_b[i]){dp[t][k][j]=max(dp[t^1][k-1][j-t_b[i]]+a[i], dp[t][k][j]);}}}}int res=0;t=t^1;for(i=l_sum; i<=sum[n]; i++){if(dp[t][K][i]>=res){res=dp[t][K][i];}}printf("%d %d", K, l_sum-res);return 0;
}
这篇关于codeforces 730J - Bottles的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
