POJ 1276 多重背包

多种物品，每种价格为p，个数为num，求所能凑成最接近且小于all的价值

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int all,n;
int p[15],num[15];
int fin[100005],used[100005];
int main()
{
    while(~scanf("%d",&all))
    {
        scanf("%d",&n);
        memset(fin,0,sizeof(fin));
        fin[0] = 1;
        for(int i = 1; i <= n; i++)
            scanf("%d%d",&num[i],&p[i]);
        for(int i = 1; i <= n; i++)
        {
            memset(used,0,sizeof(used));
            for(int j = p[i]; j <=all; j++)
            {
                if(fin[j-p[i]] && used[j-p[i]]<num[i] && !fin[j])
                {
                    fin[j] = 1;
                    used[j] = used[j-p[i]]+1;
                }
            }
        }
        for(int i = all;i >= 0;i--)
        {
            if(fin[i] == 1){
                printf("%d
",i);
                break;
            }
        }
    }
    return 0;
}