POJ 1276 Cash Machine
题意:
多重背包问题
思路:
多重背包模板
实现:
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100005;
int goods[N], f[N];
int main()
{
int m;
while (scanf("%d", &m) != EOF)
{
for (int i = 0; i <= m; i++)
f[i] = 0;
int n;
scanf("%d", &n);
while (n--)
{
int v, s;
scanf("%d%d", &s, &v);
int cnt = 1;
for (int i = 1; i <= s; i *= 2)
{
goods[cnt++] = i * v;
s -= i;
}
if (s > 0)
goods[cnt++] = s * v;
for (int i = 1; i < cnt; i++)
for (int j = m; j >= goods[i]; j--)
f[j] = max(f[j], f[j - goods[i]] + goods[i]);
}
printf("%d\n", f[m]);
}
return 0;
}
标签:goods,int,Cash,1276,Machine,POJ
From: https://www.cnblogs.com/zxr000/p/17002710.html