CD

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,a[105],pre[105][10005],dp[10005],ans[10005],top;
inline void print(int m,int n){
    if(m<=0||n<=0)return;
    if(pre[m][n]==1){
        ans[++top]=a[m];
        print(m-1,n-a[m]);
    }else print(m-1,n);
}
int main(){
    while(scanf("%d %d",&n,&m)!=EOF){
        top=0;
        memset(a,0,sizeof(a));
        memset(pre,0,sizeof(pre));
        memset(dp,0,sizeof(dp)); 
        memset(ans,0,sizeof(ans));
        for(int i=1;i<=m;i++)scanf("%d",&a[i]);
        for(int i=1;i<=m;i++){
            for(int j=n;j>=a[i];j--){
                if(dp[j-a[i]]+a[i]>dp[j]){
                    pre[i][j]=1;
                    dp[j]=dp[j-a[i]]+a[i];
                }
            }
        }
        print(m,n);
        for(int i=top;i>=1;i--)printf("%d ",ans[i]);
        printf("sum:%d\n",dp[n]);
    }
    return 0;
}

一道简单的01背包，输出sum的数值十分简单，就不多赘余。

然而对于输出序列，主要思路与输出最大上升子序列一致。

首先，我们可以使用一个pre二维数组来存储状态。
如果pre[i][j]等于1，则表示当前CD已选择，自然，是说前i张CD进行j分钟时选择了该CD。

反之pre[i][j]等于0，则未进行选择……

最后递归输出选择CD序列，详见print函数，如若选择，继续递归前i-1个CD，进行了j-a[i]分钟，建议用一个ans数组进行存储。

最后逆序输出！！！