分辣条
发布时间: 2016年6月26日 20:36 最后更新: 2016年6月26日 20:37 时间限制: 1000ms 内存限制: 128M
描述
“你喝的酸奶是我买的，辣条也是我买的，你现在要跟我分手，你把我当什么？”
“因为你每次分辣条的时候都比我多一根！”
可见分好辣条是一件多么重要的事情。。
现在有n（1<=n<=200）根辣条，每根辣条的重量为a1,a2...ai..an(1<=ai<=100)。
那么能不能把这些辣条分为重量相等的两份呢？
输入
输入有多组数据。
每组数据第一行为一个整数n（1<=n<=200），n代表辣条的数量。
第二行有n个整数，a1,a2...ai..an，其中ai(1<=ai<=100)代表第i根辣条的重量
输出
若能分成重量相等的两份，则输出"YES",否则输出"NO"每个答案占一行
样例输入1 复制
3
1 2 1
4
1 1 1 2
样例输出1
YES
NO 01背包解决恰好装满情况，利用容积与价值相等。
#include<stdio.h>
#include<string.h>
int main()
{
int n,sum,i,j;
int a[],f[];
while(~scanf("%d",&n)){
sum=;
for(i=;i<=n;i++){
scanf("%d",&a[i]);
sum+=a[i];
}
if(sum%==) printf("NO\n");
else{
sum/=;
memset(f,,sizeof(f));
for(i=;i<=n;i++){
for(j=sum;j>=;j--){
if(j-a[i]>=){
if(f[j-a[i]]+a[i]>f[j]) f[j]=f[j-a[i]]+a[i];
}
}
}
if(f[sum]==sum) printf("YES\n");
else printf("NO\n");
}
}
return ;
}
分辣条2
Description
啊啊有根很大的辣条，重量为n，啊啊想把辣条分给很多小朋友，但是必须满足下列条件：
1.每个小朋友分得的辣条重量为a,b或c；
2.分得辣条的小朋友的数量最多；
3.没有剩余的辣条，也就是说所有辣条都分完啦。
帮帮啊啊找出能分得辣条小朋友的数量。
Input
有多组数据，每组数据包含4个整数n,a,b,c（1<=n,a,b,c<=4000）
Output
每组数据输出能分得辣条的小朋友数量，每组输出占一行
Sample Input 1
5 5 3 2
Sample Output 1
2
Sample Input 2
7 5 5 2
Sample Output 2
2
Source
2015级计科纳新考试
#include<bits/stdc++.h>
#define MAX 5005
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll; int a[];
int dp[MAX]; int main()
{
int n,i,j;
while(~scanf("%d",&n)){
for(i=;i<=;i++){
scanf("%d",&a[i]);
}
memset(dp,-INF,sizeof(dp));
dp[]=;
for(i=;i<=;i++){
for(j=a[i];j<=n;j++){
dp[j]=max(dp[j],dp[j-a[i]]+);
}
}
printf("%d\n",dp[n]);
}
return ;
}