做题感悟:本来以为就一种结果搞了好久没搞定,然后用前天看的01背包打印路径的方法,但是必须用二维的数组果断超时,因为没看到第一维只有20!!。
解题思路:这题属于价值和重量相等的01背包问题,只是题目还要求输出路径(只要输出一种即可)。
代码:
#include<stdio.h> #include<string.h> int dp[10005],w[10005] ; bool path[25][10005] ; // 路径记录 int main() { int i,j,n,m ; while(scanf("%d%d",&m,&n)!=EOF) { for(i=0 ;i<n ;i++) scanf("%d",&w[i]) ; memset(path,false,sizeof(path)) ; memset(dp,0,sizeof(dp)) ; for(i=n-1 ;i>=0 ;i--) // i从n到0便于打印路径 for(j=m ;j>=w[i] ;j--) if(dp[j]<dp[j-w[i]]+w[i]) { dp[j]=dp[j-w[i]]+w[i] ; path[i][j]=true ; } j=m ; for(i=0 ;i<n ;i++) // 打印路径 if(path[i][j]) { printf("%d ",w[i]) ; j-=w[i] ; } printf("sum:%d\n",dp[m]) ; } return 0 ; }
代码:
#include<stdio.h> #include<string.h> int dp[25][10005],w[10005] ; int main() { int n,m,i,j ; while(scanf("%d%d",&m,&n)!=EOF) { for(i=1 ;i<=n ;i++) scanf("%d",&w[i]) ; memset(dp,0,sizeof(dp)) ; // 一定要有 for(i=n ;i>=1 ;i--) for(j=0 ;j<=m ;j++) { dp[i][j]=(i==n ? 0 : dp[i+1][j]) ; if(j>=w[i]&&dp[i][j]<dp[i+1][j-w[i]]+w[i]) dp[i][j]=dp[i+1][j-w[i]]+w[i] ; } j=m ; for(i=1 ;i<=n ;i++) if(dp[i][j]>dp[i+1][j]) { printf("%d ",w[i]) ; j-=w[i] ; } printf("sum:%d\n",dp[1][m]) ; } return 0 ; }