xfstart07
Get busy living or get busy dying

/*
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 阅读(187) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理