前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >UVA Dividing coins

UVA Dividing coins

作者头像
ShenduCC
发布2018-04-26 17:19:12
5570
发布2018-04-26 17:19:12
举报
文章被收录于专栏:算法修养

题目链接:

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=503

背包问题:

代码语言:javascript
复制
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>


using namespace std;
int a[105];
int dp[50005];
int t;
int n;
int num;
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		num=0;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			num+=a[i];
		}
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++)
		{
			for(int j=num;j>=a[i];j--)
			{
				dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
			}
		}
		int num2=num/2;
		int num3=0,num4=0;
		for(int i=num2;i>=1;i--)
		{
			if(dp[i]==i)
			{
                num3=i;
				break;
			}
		}
		for(int i=num2;i<=n;i++)
		{
			if(dp[i]==i)
			{
                num4=i;
				break;
			}

		}
		int ans1,ans2;
	
              ans1=num-num4-num4;
		
			  ans2=num-num3-num3;
		printf("%d\n",min(ans1,ans2));
	}
	return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2016-05-04 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档