UVA 624 CD

#include <cstdio>  
#include <iostream>  
#include<algorithm>
#include<math.h> 
#include <string.h>  
#include<vector> 
#include<queue>
using namespace std;

int dp[10005],w[30];
bool vis[10005][1005];  　　//用于标记路径

int main()
{
    int vol,n,k;
    while(scanf("%d %d",&vol,&n)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        memset(vis,0,sizeof(vis));
        
        for(int i=0;i<n;i++)
            scanf("%d",&w[i]);
        
        for(int i=0;i<n;i++)
            for(int j=vol;j>=w[i];j--)
            if(dp[j]<=dp[j-w[i]]+w[i])
            {
                dp[j]=dp[j-w[i]]+w[i];
                vis[j][i]=1;
            }
    
        for(int i=n-1,j=vol;i>=0;i--)  //打印路径
        {    
            if(vis[j][i])
            {
                printf("%d ",w[i]);
                j-=w[i];
             }
        }
        printf("sum:%d\n",dp[vol]);  
    }
    return 0;
 }