学步园

大意不再赘述。

思路：多重背包。

数组的大小根据题目的要求定，一般num数组是有少种物品开多大，V与W同样， f的大小是根据最大的cost或者weight * num[i]来定的，小于最大背包容量就行。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;

const int INF = 0x3f3f3f3f;

int f[110];
int V[110], W[110];
int num[110];

int n, C;

void init()
{
	memset(f, 0, sizeof(f));
}

void Zp(int cost, int weight)
{
	for(int v = C; v >= cost; v--)
	{
		f[v] = max(f[v], f[v-cost]+weight);
	}
}

void Cp(int cost, int weight)
{
	for(int v = cost; v <= C; v++)
	{
		f[v] = max(f[v], f[v-cost]+weight);
	}
}

void Mp(int cost, int weight, int amount)
{
	if(cost * amount >= C)
	{
		Cp(cost, weight);
		return ;
	}
	else
	{
		int k = 1;
		while(k < amount)
		{
			Zp(k*cost, k*weight);
			amount -= k;
			k *= 2;
		}
		Zp(cost*amount, weight*amount);
	}
}

int dp()
{
	for(int i = 1; i <= n; i++)
	{
		Mp(V[i], W[i], num[i]);
	}
	return f[C];
}

void read_case()
{
	init();
	scanf("%d%d", &C, &n);
	for(int i = 1; i <= n; i++)
	{
		scanf("%d%d%d", &V[i], &W[i], &num[i]);
	}
}

void solve()
{
	read_case();
	int ans = dp();
	printf("%d\n", ans);
}

int main()
{
	int T;
	scanf("%d", &T);
	while(T--)
	{
		solve();
	}
	return 0;
}