多重背包
#include <stdio.h>
#include <string.h>
#define N 105
#define MAX(a, b) (a > b ? a : b)
int p[N], h[N], c[N], f[N];
void Complete(int cost, int weight, int n)
{
for(int i = cost; i <= n; i++)
f[i] = MAX(f[i], f[i - cost] + weight);
}
void Zero_One(int cost, int weight, int n)
{
for(int i = n; i >= cost; i--)
f[i] = MAX(f[i], f[i - cost] + weight);
}
int main()
{
int t, n, m;
scanf("%d", &t);
while(t--)
{
scanf("%d %d", &n, &m);
for(int i = 0; i < m; i++)
{
scanf("%d %d %d", &p[i], &h[i], &c[i]);
}
memset(f, 0, sizeof(f));
for(int i = 0; i < m; i++)
{
int tmp = p[i] * c[i];
if(tmp > n) Complete(p[i], h[i], n);
else
{
int k = 1;
while(k < c[i])
{
Zero_One(k * p[i], k * h[i], n);
c[i] -= k;
k <<= 1;
}
Zero_One(c[i] * p[i], c[i] * h[i], n);
}
}
printf("%d\n", f[n]);
}
return 0;
}