Candy Store

Candy Store Time Limit: 30000ms, Special Time Limit:75000ms, Memory Limit:65536KB Total submit users: 6, Accepted users: 6 Problem 12624 : No special judgement Problem description You are walking with a friend, when you pass a candy store. You make a comment about how unhealthy their wares are. Your friend issues an interesting challenge: who can be the unhealthiest? Both of you will go into the store with the same amount of money. Whoever buys candy with the most total calories wins!

Since you’re a smart computer scientist, and since you have access to the candy store’s inventory, you decide not to take any chances. You will write a program to determine the most calories you can buy. The inventory tells you the price and calories of every item. It also tells you that there is so much in stock that you can buy as much of any kind of candy as you want. You can only buy whole pieces of candy.

Input There will be multiple test cases in the input. Each test case will begin with a line with an integer n (1 ≤ n ≤ 5,000), and an amount of money m ($0.01 ≤ m ≤ $100.00), separated by a single space, where n is the number of different types of candy for sale, and m is the amount of money you have to spend. The monetary amount m will be expressed in dollars with exactly two decimal places, and with no leading zeros unless the amount is less than one dollar. There will be no dollar sign. Each of the next nlines will have an integer c (1 ≤ c ≤ 5,000) and an amount of money p ($0.01 ≤ p ≤ $100.00), separated by a single space, where c is the number of calories in a single piece of candy, and p is the price of a single piece of candy, in dollars and in the same format as m. The input will end with a line containing ‘0 0.00’.

Output For each test case, output a single integer, indicating the maximum amount of calories you can buy with up to m dollars. Output no spaces, and do not separate answers with blank lines.

Sample Input

2 8.00 700 7.00 199 2.00 3 8.00 700 7.00 299 3.00 499 5.00 0 0.00

Sample Output

796 798

Problem Source

ACM ICPC Southeast USA Regional Programming Contest 2012

完全背包。注意浮点数转化成整数时的精度！用floor转化一下~

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int w[5009], C[5009];
long long f[10009];
double c[5009];
double eps = 1e-9;
int main(void)
{
//  freopen("in.txt", "r", stdin);
  int n;
  double m;
  while (~scanf("%d%lf", &n, &m)) {
      if (n+m<eps) break;
    for (int i = 0; i < n; ++i) scanf("%d%lf", w+i, c+i), C[i]=(floor)(c[i]*100);
    memset(f, 0, sizeof(f));
    int S = (floor)(m * 100);
    for (int i = 0; i< n; ++i)
      for (int v = C[i]; v <= S; ++v)
        if (f[v] < f[v-C[i] ] + w[i]) f[v] = f[v-C[i] ] + w[i];
    printf("%lld\n", f[S]);
  }
  return 0;
}

嗨，中村。