uva 01背包记录路径

反正我是不会，抄别人的代码的 #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<string> #include<cstring> #include<iomanip> #include<iostream> #include<stack> #include<cmath> #include<map> #include<vector> #define ll long long #define inf 0x3f3f3f3f using namespace std; const int maxn=25; //2017-3-12 21:18:32 int w[maxn]; int dp[10001]; int vis[23][10001]; int ans[maxn]; int cnt; void init(){ memset(dp,0,sizeof(dp)); memset(vis,0,sizeof(vis)); } void output(int n,int sum){ if(n==0)return ; if(vis[n][sum]==0){ output(n-1,sum); } else{ output(n-1,sum-w[n]); ans[cnt++]=w[n]; } } int main(){ int sum,n; while(scanf("%d%d",&sum,&n)!=EOF){ for(int i=1;i<=n;++i){ scanf("%d",&w[i]); } init(); vis[0][0]=1; for(int i=1;i<=n;++i){ for(int j=sum;j>=w[i];j--){ dp[j]=max(dp[j-w[i]]+w[i],dp[j]); if(dp[j]==dp[j-w[i]]+w[i]) vis[i][j]=1; } } cnt=0; output(n,sum); for(int i=0;i<cnt;++i) cout<<ans[i]<<' '; cout<<"sum:"<<dp[sum]<<'\n'; } }