题解
其实转化一下就可以变成一个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}}。