Candy |
||
题目描述Henry和Lena最近买了很多各种各样的糖…他们决定把所有糖分了… 但是两个人都不希望自己糖的总重量比对方少太多， 鉴于不同的糖的味道不尽相同，所以每个糖都有一个yummy值。 Henry希望知道在两人得到的糖总质量差不大于m的时候，自己的糖yummy值之和的尽量大。 输入有多组数据 每组数据第一行为两个整数，n，m，(1 <=n <= 100， 0 <= m <= 500) 接下来有两行，每行有n个数，第一行的第i个数表示第i颗糖的重量xi（ 0 < xi <= 100）， 第二行的第i个数表示第i颗糖的yummy值 yi( 0 < yi <= 100 ) 输出每行输出一组数据的结果， 一个数表示Henry的糖的总yummy值的最大值，如果不存在如题所述的分糖方案，输出-1
样例输入1 30 43 15 2 290 89 22 76 77 样例输出-1 153 |
代码：
/**
* 01背包 先全部装入再判断是否满足条件
* 条件： | A - B | <= m
* A + B = sum
* 得到： | sum - 2*B | <= m
*
*/
#include <stdio.h>
#include <string.h>
#include <limits.h>
#define maxn 20005
int max(int a, int b)
{
if (a > b)return a;
return b;
}
int abs(int a)
{
if (a > 0)return a;
return -a;
}
int main()
{
int n, m;
int x[maxn], y[maxn], dp[maxn];
while (scanf("%d%d", &n, &m) != EOF)
{
memset(dp, -1, sizeof(dp));
dp[0] = 0;
int sum = 0;
for (int i = 1; i <= n; i++){
scanf("%d", &x[i]);
sum += x[i];
}
for (int i = 1; i <= n; i++)
scanf("%d", &y[i]);
for (int i = 1; i <= n; i++)
{
for (int v = sum; v >= x[i]; v--){
if (dp[v - x[i]] >= 0)
dp[v] = max(dp[v], dp[v - x[i]] + y[i]);
}
}
int ans = INT_MIN;
for (int v = 0; v <= sum; v++)
if (abs(sum - 2 * v) <= m)
ans = max(ans, dp[v]);
printf("%d\n", ans);
}
return 0;
}