HU 2546:食事カード(01バックパック)

HU 2546:食事カードhttp://acm.hdu.edu.cn/showproblem.php?pid=2546
問題があったら、物体の価値と順序を選択する必要があります.順序を並べてから、その01に対して処理します.この問題は私達が小さい時は先に注文すればするほど5に近くなります.そして一回に最大値を取ると、私達が使うお金はもっと多くなります.

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<string>

using namespace std;

#define N 1005

int dp[N+50];

int main(void)

{

    int num[N];

    int n,m;

    int i,j;

    while(cin>>n&&n!=0){

        for(i=1;i<=n;i++) cin>>num[i];

        cin>>m;

        memset(dp,0,sizeof(dp));

        dp[0]=1;

        int ma=0;

        sort(num+1,num+1+n);

        for(i=1;i<=n;i++){

            for(j=m+45;j>=0;j--){

                if((m-j)>=5&&dp[j]){ 

                    dp[j+num[i]]=1;

                    ma=max(ma,j+num[i]);

                }

            }

        }

        

        cout<<m-ma<<endl;

    }

    return 0;

}