题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) sh代码 $O(n^2)$
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N = 1e4 ;
int v[N];
int f[40][2*N];
int main()
{
int n,m;
cin >> m >>n;
for(int i = 1;i <= n; i++) cin >> v[i];
for(int i = 1;i <= n; i ++)
for(int j = 1; j <= m; j++)
{
f[i][j] = f[i-1][j];
if(j >= v[i])
f[i][j] = max(f[i][j], f[i-1][j-v[i]]+v[i]);
}
cout<<m-f[n][m]<<endl;
return 0;
}
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(优化代码)
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N = 1e4 ;
int v[N];
int f[2*N];
int main()
{
int n,m;
cin >> m >>n;
for(int i = 1;i <= n; i++) cin >> v[i];
for(int i = 1;i <= n; i ++)
for(int j = m; j >= v[i]; j--)
{
f[j] = max(f[j], f[j-v[i]]+v[i]);
}
cout<<m-f[m]<<endl;
return 0;
}
时间复杂度
参考文献
C++ 代码
blablabla