1 条题解

  • 0
    @ 2024-12-24 10:06:14

    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
    上传者