01背包，由于要输出方案，所以还要在dp的同时，保存一下路径。
#include <iostream>
#include <stdio.h>
#include <string.h>
/*
AC
01背包+输出方案
答案不唯一，就像样例中的
45 8 4 10 44 43 12 9 8 2
题目给出的输出4 10 12 9 8 2 sum:45
输出43 2 sum:45 也是可以的
题目中没要求按照什么顺序输出，输出一种方案即可 */
using namespace std;
const int maxm=;
const int maxn=;
int n,m;
int cd[maxm];
int dp[maxn];
struct Node{
int idx; //若idx为0，表示当前物品没有被选择，否则即为选择了
int pre; //设立前驱，即 不装当前物品时的背包容量的大小
}node[maxm][maxn]; //node[i][j]:i表示当前物品的编号，j表示当前的背包容量
int main()
{
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=;i<=m;i++){
scanf("%d",&cd[i]);
}
for(int i=;i<=m+;i++){
for(int j=;j<=n+;j++)
node[i][j].idx=node[i][j].pre=;
}
memset(dp,,sizeof(dp));
//原本以为选择的CD要按原来的顺序输出，才将i逆序
//结果改成从正序循环，照样AC
//而且题目中也没要求按照什么顺序输出，打印一种结果即可
for(int i=m;i>=;i--){
//注意这里j要从n到1
for(int j=n;j>;j--){
if(j>=cd[i] && dp[j-cd[i]]+cd[i]>dp[j]){
dp[j]=dp[j-cd[i]]+cd[i];
node[i][j].idx=i; //选择了当前物品
node[i][j].pre=j-cd[i]; //指向node[i+1][j-cd[i]]
}
else{
node[i][j].idx=; //当前物品没有被选择
node[i][j].pre=j; //指向node[i+1][j]
}
}
}
int tmp=n,k=;
while(k<=m){
if(node[k][tmp].idx!=)
printf("%d ",cd[k]);
tmp=node[k][tmp].pre;
k++;
}
printf("sum:%d\n",dp[n]);
}
return ;
}