题目描述
blablabla
样例
blablabla
算法1
(背包问题)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
int k,n;
int a[N],f[N];
int main()
{
memset(f,0x3f3f3f3f,sizeof f);
cin>>k>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
f[0]=0;
for(int i=1;i;i++)
{
for(int j=1;j<=n;j++)
if(a[j]<=i)
f[i]=min(f[i],f[i-a[j]]+1);
if(f[i]>k)
{
cout<<i-1;
break;
}
}
return 0;
}
错误算法
(贪心)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
int k,n;
int a[N];
int main()
{
cin>>k>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+n+1);
// cout<<a[n];
for(int i=1;i;i++)
{
int res=0;
int v=i;
for(int j=n;j>=1;j--)
{
while(a[j]<=v)
{
res+=v/a[j];
v%=a[j];
}
}
if(res>k)
{
cout<<i-1;
return 0;
}
}
return 0;
}