首页 > ACM题库 > HDU-杭电 > HDU 1587 Flowers-背包问题-[解题报告] c-sharp
2013
12-12

HDU 1587 Flowers-背包问题-[解题报告] c-sharp

Flowers

问题描述 :

As you know, Gardon trid hard for his love-letter, and now he’s spending too much time on choosing flowers for Angel.
When Gardon entered the flower shop, he was frightened and dazed by thousands kinds of flowers.
"How can I choose!" Gardon shouted out.
Finally, Gardon– a no-EQ man decided to buy flowers as many as possible.
Can you compute how many flowers Gardon can buy at most?

输入:

Input have serveral test cases. Each case has two lines.
The first line contains two integers: N and M. M means how much money Gardon have.
N integers following, means the prices of differnt flowers.

输出:

For each case, print how many flowers Gardon can buy at most.
You may firmly assume the number of each kind of flower is enough.

样例输入:

2 5
2 3

样例输出:

2

Hint
Hint
Gardon can buy 5=2+3,at most 2 flower, but he cannot buy 3 flower with 5 yuan.

#include<iostream>
#include<cstdio>
#define Max 100001
using namespace std;
int f[Max],bag,c[1001];
void MultiplePack(int cost,int weight)
{
     for(int i=cost;i<=bag;i++)
        if(f[i]<f[i-cost]+weight)
           f[i]=f[i-cost]+weight;
}
int main()
{
    int n;
    while(scanf("%d%d",&n,&bag)!=-1)
    {
         for(int i=1;i<=n;i++)
           scanf("%d",&c[i]);
         memset(f,0,sizeof(f));
         for(int i=1;i<=n;i++)
            MultiplePack(c[i],1);
         printf("%d/n",f[bag]);
    }
    return 0;
}

解题报告转自:http://blog.csdn.net/once_hnu/article/details/6249233