boj1490 找零钱 dp

找零钱
Submit: 441   Accepted:65
Time Limit: 1000MS  Memory Limit: 65535K
Description
和女朋友外出就餐时，备足零钱是很有必要的。当饭后结账时，服务员没有足够的零钱找给你，怎么办呢？服务员是绝对不会少收钱的，当然，你可以给他一些小费来省去找钱的麻烦。但是，如果你给的消费太多，女朋友会不高兴的。现在轮到你来决策了。

Input
输入的第一行包含一个整数c，表示测试数据的组数。
每组数据的第一行包含一个整数n，分别表示你要付的钱的数目（1<=n<=10000）。
第二行包含一个整数m表示你身上的零钱的数目（1<=m<=100）。
接下来m行，每行包含一个整数：x表示你身上的钱币的面值 (1<=x<=10000)。你身上的钱的价值总和不小于要付的钱。


Output
对每组数据，输出两个整数，分别表示最后付钱的价值和钱币的数量如果相同价值输出最小数量。

Sample Input

1
1400
3
500
1000
2000


Sample Output

1500 2



类似于背包的dp，也可以看作是dp备忘录，将前面算得的最优值存到stat[]数组里，每次要加入新值时，到stat[]数组里遍历，求出加入后的值，如果更优，则更新stat[]中的相应项

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

#define MAX_INT 0x7fffffff

typedef struct _stat
{
    int money;
    int cnt;
}ST_STAT;

int cas, n, m, x;
ST_STAT stat[10010];
vector<ST_STAT> v_larger;

/* 在大于n的集合中查找最小值 */
void find_min()
{
    ST_STAT min;
    min.money = MAX_INT;
    min.cnt = MAX_INT;

    vector<ST_STAT>::iterator beg, end;
    end = v_larger.end();
    for (beg = v_larger.begin() ; beg != end ; beg++)
    {
        if (beg->money < min.money)
            min = *beg;
        else if (beg->money == min.money)
        {
            if (beg->cnt < min.cnt)
            {
                min = *beg;
            }
        }
    }

    printf("%d %d\n", min.money, min.cnt);
    
}

void dp(int size)
{
    int i, j, k, idx;
    ST_STAT temp;

    for (i=0 ; i<size ; i++)
    {
        scanf("%d", &x);
        /* 从后向前寻找最优值，如果从前往后的话，更新的值会覆盖原值(背包中也用过类似的思路) */
        for (j=n-1 ; j>=0 ; j--)
        {
            if (-1 == stat[j].money)
                continue;

            idx = x + stat[j].money;
            /* 钱数已经超过n,将其加入到vector中，等待后面在v中寻找最优值 */
            if (idx >= n)
            {
                temp.money = idx;
                temp.cnt = stat[j].cnt + 1;
                v_larger.push_back(temp);
                continue;
            }

            /* 这个钱数以前已经出现过，看是否需要更新 */
            if (-1 != stat[idx].money)
            {
                if (stat[j].cnt + 1 < stat[idx].cnt)
                {
                    stat[idx].cnt = stat[j].cnt + 1;
                }
            }
           
            /* 这个值没有出现过，直接更新 */
            else
            {
                stat[idx].money = idx;
                stat[idx].cnt = stat[j].cnt + 1;
            }
        }
        /*
        printf("stat:");
        for (k=0 ; k         {
            printf("%d %d, ", stat[k].money, stat[k].cnt);
        }
        printf("\n");
        */
       
    }

    find_min();
}

int main(int argc, char *argv[])
{
    int i;

    scanf("%d", &cas);
    while (cas--)
    {
        scanf("%d", &n);
        scanf("%d", &m);
        memset(stat, 0, sizeof(stat));
        v_larger.clear();
        for (i=1 ; i<=n ; i++)
            stat[i].money = -1;
        stat[0].money = stat[0].cnt = 0;
       
        dp(m);
    }
}