Codeforces 730J:Bottles(背包dp)

http://codeforces.com/problemset/problem/730/J

题意:有n个瓶子,每个瓶子有一个当前里面的水量,还有一个瓶子容量,问要把所有的当前水量放到尽量少的瓶子里至少需要几个瓶子,还有最少需要倒的水量(把一个瓶子的水倒到另一个瓶子的总水量)。

思路:是一个背包dp,dp[i][j] 表示选择i个瓶子容量为j的时候当前拥有的最大的水量。不过第三层循环当时不知道应该怎么写。

 #include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <iostream>
#include <stack>
#include <map>
#include <queue>
#include <set>
using namespace std;
typedef long long LL;
#define N 105
#define INF 0x3f3f3f3f
struct node {
int a, b;
} p[N];
int dp[N][N*N]; // dp[i][j] 表示选择i个瓶子容量为j的时候当前拥有的最大的水量
bool cmp(const node &a, const node &b) { return a.b > b.b; }
int main()
{
int n, sum = , tmp, cnt = , tol = , ans = ;
scanf("%d", &n);
for(int i = ; i <= n; i++) scanf("%d", &p[i].a), sum += p[i].a;
for(int i = ; i <= n; i++) scanf("%d", &p[i].b), tol += p[i].b;
tmp = sum;
sort(p + , p + + n, cmp);
for(int i = ; i <= n; i++) {
tmp -= p[i].b;
if(tmp <= ) { cnt = i; break; } // 确定最终的瓶子数
}
memset(dp, -, sizeof(dp));
dp[][] = ;
for(int i = ; i <= n; i++) {
for(int j = tol; j >= p[i].b; j--) { // 类似01背包
for(int k = i; k > ; k--) { // 之前选择的状态再加上目前的第i个瓶子能否得到优化,这样就可以枚举所有情况了
if(dp[k-][j-p[i].b] != -) { // 如果上一个状态有解
dp[k][j] = max(dp[k][j], dp[k-][j-p[i].b] + p[i].a);
}
}
}
}
for(int i = sum; i <= tol; i++)
ans = max(ans, dp[cnt][i]);
printf("%d %d\n", cnt, sum - ans);
return ;
}
上一篇:[文件]Linux文本处理常用命令总结


下一篇:HDU2191--多重背包(二进制分解+01背包)