hrbust 哈理工 2252 完全背包模板题

理工 2252 完全背包模板题"/>

hrbust 哈理工 2252 完全背包模板题

世界

Time Limit: 10000 MS Memory Limit: 32768 K Total Submit: 151(51 users) Total Accepted: 56(41 users) Rating:  Special Judge: No

Description

世界是一个非常软弱的女孩子，会在关键的时刻临阵退缩呢。你为了帮助她，让她去争取自己的幸福 ，就要给她注入叫做勇气的东西！注入不同数量的勇气的花费是不一样的，那么让世界的勇气值大于 等于m的最少花费是多少呢？

Input

输入数据的第一行包括了一个整数T，表示数据的组数。 每组数据的第一行，包括了两个整数n(1≤n≤100)和m(1≤m≤1000)，表示勇气的种类和世界需要的勇气值。 接下来的n行，每行包括两个整数costi(1≤costi≤10)和wi(1≤wi)分别表示，第i种勇气的花费和产生的勇气值。每种可以产生勇气的药剂有无限个。

Output

每组数据的输出包括一行，表示最小的花费。

Sample Input

2 1 2 10 3 2 10 100 10 1 1

Sample Output

10 10

Source

“尚学堂杯”2015级程序设计竞赛(10月)热身赛

Author

TwIStOy

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        int a[10003],b[10003];
        scanf("%d%d",&n,&m);
        for(int i=0; i<n; i++)
        {
            scanf("%d%d",&a[i],&b[i]);
        }
        for(int i=1;; i++)
        {
            int flag=0;
            int dp[i+1];
            memset(dp,0,sizeof(dp));
            for(int j=0; j<n; j++)
            {
                if(flag)break;
                for(int k=a[j]; k<=i; k++)
                {
                    dp[k]=max(dp[k],dp[k-a[j]]+b[j]);
                    if(dp[k]>=m)
                    {
                        flag=1;
                        break;
                    }
                }
            }
            if(flag)
            {
                printf("%d\n",i);
                break;
            }
        }
    }
}