洛谷CF433A题解

damage

题解

其实转化一下就可以变成一个01背包问题，物品价值就等于物品的重量。

设苹果的重量和为sum，那么只要转化为一个具有如下条件的01背包：

背包容量为\frac{1}{2}sum
物品数量为n
物品的重量与价值都分别等于苹果的重量

然后dp一下就可以了，如果背包容量为\frac{1}{2}sum时无法装满（\ne\frac{1}{2}sum）。

代码

#include<stdio.h>
#include<iostream>
int n,w[105],sum,f[10010];
int main()
{
	scanf("%d",&n);
	for(register int i=1;i<=n;++i)
	{
		scanf("%d",&w[i]);
		sum+=w[i]; //求苹果总质量
	}
	sum>>=1; //为了方便计算先把sum/2
	for(register int i=1;i<=n;++i)
		for(register int j=sum;j>=w[i];j--) f[j]=std::max(f[j],f[j-w[i]]+w[i]); //使用滚动数组的01背包
	if(f[sum]==sum) printf("YES\n"); //判断
	else printf("NO\n");
	return 0;
}

说明

关于本篇涉及到的位运算的讲解（其实就一个，大佬们肯定都会）

x>>1表示x/2，其实x>>i =\frac{x}{2^{i}}。