HDU 2546食事カード(ベース01リュック)

【タイトルリンク】:click here~~
【考え方】カードで商品が買えるようにするには、残高を計算して5を引いた後、前のn-1個の商品を買うことができる最大価値(価格の増加順)を計算し、最後に最大の価格を減らせばよい
コード:

/*
* Problem: HDU No.2546
* Running time: 46MS
* Complier: C++
* Author: javaherongwei
* Create Time: 11:26 2015/9/5    
*/

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N=1005;
int dp[N];
int value[N],volume[N];
int n,V;
int main()
{
    while(scanf("%d",&n),n)
    {
        memset(dp,0,sizeof(dp));
        memset(value,0,sizeof(value));
        memset(volume,0,sizeof(volume));
        int maxx=0;
        for(int i=0; i<n; ++i)
        {
            scanf("%d",&volume[i]);
            maxx=max(volume[i],maxx);
        }
        scanf("%d",&V);
        sort(volume,volume+n);
        if(V>=5)
        {
            for(int i=0; i<n-1; ++i)
            {
                for(int v=V-5; v>=volume[i]; --v)
                {
                    dp[v]=max(dp[v],dp[v-volume[i]]+volume[i]);
                }
            }
            printf("%d
",V-dp[V-5]-volume[n-1]);
        }
        else printf("%d
",V);
    }
    return 0;
}

/*
Sample Input
1
50
5
10
1 2 3 2 1 1 2 3 2 1
50
0

Sample Output
-45
32
*/