描述
Roger是个养鸭专业户。他卖鸭子时为了方便管理,用一些笼子来装鸭子。同一个大小的笼子装同样多的鸭子,不同大小的笼子装不同数目的鸭子。我们假设他有大、中、小三种笼子。大笼子10个鸭子一笼,中笼子6个鸭子一笼,小笼子3个鸭子一笼。如果有人要买32只鸭子,Roger就会给他两个大笼,一个中笼和两个小笼。但是,Roger永远无法满足需要1、2、4、5、7、8、11、14或17只鸭子的买者。你发现,这对Roger的市场影响很大。作为好朋友,你会向他提建议希望他能改进一下。为了突出改进的必要性,你需要将问题说得非常严重才行。你不会告诉他,“你不能卖一只或者两只鸭子给买鸭子的人”;你会告诉他,“天哪!你竟然无法满足一个要买17只鸭子的大户”。也就是说,你需要告诉他他不能满足的最大的鸭子需求量是多少。 现在,你得知,Roger有n种大小不同的笼子,每种笼子里装Ai只鸭子。你需要编写程序计算,最大的不能用这些笼子凑出的鸭子数是多大。
输入
数据的第一行是一个数n,代表Roger的笼子种数; 以下n行每行一个数,其中第i行表示第i种笼子装的鸭子数Ai。
1<=n<=10
1<=Ai<=256
输出
输出最大的不能满足的鸭子需求量。 如果所有的鸭子需求量都能满足或者不存在最大的不能满足的需求量,请输出0。 我们的答案保证不超过80000。
样例输入
3
3
6
10
样例输出
17
这题我是用动态规划完全背包求解的,但不知道那错了,求条
#include<bits/stdc++.h>
using namespace std;
long long dp[220000],a[400000],b[400000],m,n,k,ff[5]={0,3,6,10};
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i],m+=a[i];
sort(a+1,a+n+1);
for(int i=1;i<=3;i++)
for(int j=1;j<=n;j++)
for(int s=1;s<=m;s++)
dp[s]=max(dp[s],dp[s-a[j]]+ff[i]);
for(int i=m;i>=a[1];i--) b[dp[i]]++;
for(int i=m;i>=a[1];i--) {
if(b[i]==0) {
cout<<i;
return 0;
}
}
cout<<0;
return 0;
}