/*
PROG: milk4
LANG: C++
*/
#include
<
cstdio
>
#include
<
cstring
>
#include
<
cstdlib
>
using
namespace
std;
int
V,N;
int
len;
int
ans;
int
a[
101
];
int
use[
101
];
bool
vis[
20001
];
int
cmp(
const
void
*
x,
const
void
*
y){
return
*
(
int
*
)x
-*
(
int
*
)y;
}
void
init()
{
scanf(
"
%d%d
"
,
&
V,
&
N);
for
(
int
i
=
1
;i
<=
N;
++
i)
scanf(
"
%d
"
,a
+
i);
qsort(a
+
1
,N,
sizeof
(
int
),cmp);
}
void
out
()
{
printf(
"
%d
"
,len);
for
(
int
i
=
1
;i
<=
len;
++
i)
printf(
"
%d
"
,use[i]);
printf(
"
\n
"
);
exit(
0
);
}
void
DP()
{
memset(vis,
0
,
sizeof
(vis));
/*
vis[0]=1;
*/
for
(
int
i
=
1
;i
<=
V
/
use[
1
];
++
i)
vis[i
*
use[
1
]]
=
1
;
for
(
int
i
=
2
;i
<=
len;
++
i)
for
(
int
j
=
use[i];j
<=
V;
++
j)
vis[j]
=
vis[j]
|
vis[j
-
use[i]];
if
(vis[V])
out
();
}
//
完全背包
void
dfs(
int
pre)
{
if
(len
==
ans)
DP();
else
{
len
++
;
for
(
int
i
=
pre;i
<=
N;
++
i){
use[len]
=
a[i];
dfs(i
+
1
);
}
--
len;
}
}
void
DFSID()
{
len
=
0
;
for
(ans
=
1
;ans
<=
N;
++
ans)
dfs(
1
);
}
int
main()
{
freopen(
"
milk4.in
"
,
"
r
"
,stdin);
freopen(
"
milk4.out
"
,
"
w
"
,stdout);
init();
DFSID();
return
0
;
}
/*
Executing
Test 1: TEST OK [0.000 secs, 2824 KB]
Test 2: TEST OK [0.011 secs, 2824 KB]
Test 3: TEST OK [0.000 secs, 2824 KB]
Test 4: TEST OK [0.000 secs, 2824 KB]
Test 5: TEST OK [0.011 secs, 2824 KB]
Test 6: TEST OK [0.011 secs, 2824 KB]
Test 7: TEST OK [0.140 secs, 2824 KB]
Test 8: TEST OK [0.054 secs, 2824 KB]
Test 9: TEST OK [0.043 secs, 2824 KB]
Test 10: TEST OK [0.292 secs, 2824 KB]
*/
/*
DP优化后
Executing
Test 1: TEST OK [0.011 secs, 2824 KB]
Test 2: TEST OK [0.000 secs, 2824 KB]
Test 3: TEST OK [0.000 secs, 2824 KB]
Test 4: TEST OK [0.011 secs, 2824 KB]
Test 5: TEST OK [0.000 secs, 2824 KB]
Test 6: TEST OK [0.000 secs, 2824 KB]
Test 7: TEST OK [0.130 secs, 2824 KB]
Test 8: TEST OK [0.032 secs, 2824 KB]
Test 9: TEST OK [0.032 secs, 2824 KB]
Test 10: TEST OK [0.184 secs, 2824 KB]
*/
DP:
/*
PROG: milk4
LANG: C++
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int Q,N;
int a[101];
int f[20001];
int pre_f[20001]={0};
int pre_v[20001]={0};
bool ans[101]={0};
int cmp(const void* x,const void* y)
{
return *(int*)y-*(int*)x;
}
void init()
{
scanf("%d%d",&Q,&N);
for(int i=1;i<=N;++i)
scanf("%d",a+i);
qsort(a+1,N,sizeof(int),cmp);
}
bool check(int i,int j)
{
while(i&&j)
{
if(pre_f[i]>pre_f[j])
return 1;
if(pre_f[i]<pre_f[j])
return 0;
i=pre_v[i];
j=pre_v[j];
}
return 0;
}
void solve()
{
memset(f,0x7F,sizeof(f));
f[0]=0;
for(int i=1;i<=N;++i)
for(int j=0;j<=Q;++j)
for(int d=1;;++d){
int now=j+a[i]*d;
if(now>Q) break;
if(f[now]>f[j]+1||
((f[now]==f[j]+1)&&((i>pre_f[now])||(i==pre_f[now]&&check(j,pre_v[now]))))){
f[now]=f[j]+1;
pre_f[now]=i;
pre_v[now]=j;
}
}
}
void out()
{
for(int i=Q;i;i=pre_v[i])
ans[pre_f[i]]=1;
printf("%d",f[Q]);
for(int i=N;i>=1;--i)
if(ans[i])
printf(" %d",a[i]);
printf("\n");
}
int main()
{
freopen("milk4.in","r",stdin);
freopen("milk4.out","w",stdout);
init();
solve();
out();
return 0;
}
/*
Executing
Test 1: TEST OK [0.022 secs, 3032 KB]
Test 2: TEST OK [0.000 secs, 3032 KB]
Test 3: TEST OK [0.000 secs, 3032 KB]
Test 4: TEST OK [0.011 secs, 3032 KB]
Test 5: TEST OK [0.032 secs, 3032 KB]
Test 6: TEST OK [0.022 secs, 3032 KB]
Test 7: TEST OK [0.011 secs, 3032 KB]
Test 8: TEST OK [0.054 secs, 3032 KB]
Test 9: TEST OK [0.022 secs, 3032 KB]
Test 10: TEST OK [0.054 secs, 3032 KB]
*/
posted on 2009-07-17 16:47
xfstart07 阅读(186)
评论(0) 编辑 收藏 引用