poj 1276 多重背包

#include <iostream>
using namespace std;
int cash, n, m[13], d[13];
int f[100100];
int money, i, v, temp, k;
int solve() {
 memset(f, 0, sizeof(f));
 money = 0;
 f[0] = 1;
 for (i=1; i <= n; i++) {
  for (v=cash; v >=0; v--) {
   if (f[v]) {
    for (k=1; k <= m[i]; k++) {
     temp = v + k*d[i];
     if (temp > cash) break;
     if (temp > money) money = temp;
     f[temp] = 1;
    }
   }
  }
 }
 return money;
}
int main()
{
 while (scanf("%d %d", &cash, &n) != EOF) {
  for (i=1; i <= n; i++) {
   scanf("%d %d", &m[i], &d[i]);
  }
  printf("%d\n", solve());
 }
 return 0;
}

poj 1276 多重背包,布布扣,bubuko.com

poj 1276 多重背包

原文：http://www.cnblogs.com/2014acm/p/3918929.html