1 条题解
-
0
C++ :
#include<stdio.h> #include<stdlib.h> #include<iostream> #include<stdio.h> #include<algorithm> using namespace std; int cmp(int a,int b){ return a > b; } int dp[10001][101],pre[10001][101]; int arr[10001],ans[10001]; int main(){ int i,j,n,m; while(scanf("%d %d",&n,&m)!=EOF){ for(i=1;i<=n;i++){ scanf("%d",&arr[i]); } sort(arr + 1, arr + n + 1,cmp); for(i=0;i<=n;i++){ for(j=0;j<=m;j++){ dp[i][j]=0; pre[i][j]=0; } } for(i=0;i<=n;i++){ dp[i][0]=1; } for(i=1;i<=n;i++){ for(j=arr[i];j<=m;j++){ if(dp[i-1][j-arr[i]]){ dp[i][j]=1; pre[i][j]=1; } else{ dp[i][j]=dp[i-1][j]; } } } if(!dp[n][m]){ printf("No Solution\n"); } else{ int cnt=0; while(n>0){ if(pre[n][m]){ ans[cnt]=arr[n]; m=m-arr[n]; n=n-1; cnt++; } else{ n--; } } for(i=0;i<cnt-1;i++){ printf("%d ",ans[i]); } printf("%d\n",ans[cnt-1]); } } return 0; }
- 1
信息
- ID
- 2474
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者