首页 > 其他 > 详细

XTU 1198 Candy

时间:2014-05-20 15:07:09      阅读:399      评论:0      收藏:0      [点我收藏+]

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;
}


XTU 1198 Candy,布布扣,bubuko.com

XTU 1198 Candy

原文:http://blog.csdn.net/u012964281/article/details/26287919

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!