PAT甲级1068.

目录

A1068

题目

样例

样例1

输入:

8 9
5 9 8 7 2 3 4 1

输出:

1 3 5

样例2

输入:

4 8
7 2 4 3

输出:

No Solution

思路和坑点

　　0-1背包问题，这里仅给出参考代码，倒是可以理解，可是我真的自己写不出来啊，考完试再认真研究吧。
　　这里给一个链接帮助理解背包问题的动态规划的原理，这样讲0-1背包太生动了

AC代码

#include<bits/stdc++.h>
using namespace std;
//0-1背包问题 
int w[10004],dp[103]={0};
bool flag[10004]={false};
bool choice[10004][103]={false};
bool cmp(int a,int b){
    return a>b;
}
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    

    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&w[i]);
    }
    sort(w+1,w+n+1,cmp);
    for(int i=1;i<=n;i++){
        for(int v=m;v>=w[i];v--){
            if(dp[v]<=dp[v-w[i]]+w[i]){    //如果放入i 
                dp[v]=dp[v-w[i]]+w[i];
                choice[i][v]=true;
            }
        }
    }
    if(dp[m]!=m)
        puts("No Solution");
    else{
        int k=n,num=0,v=m;
        while(k>0){
            if(choice[k][v]==true){
                flag[k]=true;
                v-=w[k];
                num++;
            }
            k--;
        }
        
        for(int i=n;i>=1;i--){
            if(flag[i]){
                printf("%d",w[i]);
                num--;
                if(num>0) putchar(' ');
            }
        }
    }
    return 0;    
}