题目链接：传送门

       做这道题的时候不知道怎么输出路径，然后我就很麻烦的先用01背包把能装下的最大值求出来，然后用这个最大值去用递归输出路线，很麻烦，然后看了别人的代码，发现可以在更新dp[j]的值的时候记录下当前的dp[i][j]。

先上之前的我写的递归输出路径的代码：

AC代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n,m,num;
int pre[1005];
int dp[1005];
int a[1005];
int flag;

void Output(){
  for(int i=0;i<num;i++)
  printf("%d ",a[i]);
  flag = 1;
  return ;
}

void dfs(int x,int sum){
  if(sum == dp[n]){
    Output();
    return ;
  }
  if(flag == 1)return ;
  if(sum > dp[n])return ;
  for(int i=x;i<m;i++){

    a[num++] = pre[i];
    dfs(i+1,sum+pre[i]);
    if(flag == 1)return ;
    num--;
  }
  return ;
}

int main()
{
  while(~scanf("%d%d",&n,&m)){
    flag = 0;
    for(int i=0;i<m;i++){
      scanf("%d",&pre[i]);
    }
    memset(dp,0,sizeof(dp));
    for(int i=0;i<m;i++){
      for(int j=n;j>=pre[i];j--){
        dp[j] = max(dp[j],dp[j - pre[i]] + pre[i]);
      }
    }
    num = 0;
    dfs(0,0);
    printf("sum:%d\n",dp[n]);
  }
  return 0;
}

然后是简单的标记输出路径代码：

AC代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n,m,num;
int pre[10005];
int dp[10005];
int a[10005][10005];
int flag;

int main()
{
  while(~scanf("%d%d",&n,&m)){
    flag = 0;
    for(int i=0;i<m;i++){
      scanf("%d",&pre[i]);
    }
    memset(a,0,sizeof(a));
    memset(dp,0,sizeof(dp));
    for(int i=m-1;i>=0;i--){
      for(int j=n;j>=pre[i];j--){
        if(dp[j] < dp[j - pre[i]] + pre[i]){
        dp[j] = dp[j - pre[i]] + pre[i];
        a[i][j] = 1;
      }
    }
  }
    for(int i=0,j=n;i<m;i++){
      if(a[i][j]){
        printf("%d ",pre[i]);
        j -= pre[i];
      }
    }
    printf("sum:%d\n",dp[n]);
  }
  return 0;
}