虽然每件物品的数目并不是1,可能有多个,但我们完全可以把这个题目转化成01背包来解决。 可以把多件相同的物品合并成一件,马上就变01背包了。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int dp[105];
int pr[105];
int cnt[105];
int w[105];
int main()
{
int n, m, t;
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
{
scanf("%d %d %d", &pr[i], &w[i], &cnt[i]);
}
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= m; i++)
{
for (int j = n; j >= 0; j--)
{
for (int k = 1; k <= cnt[i]; k++)
{
if (j >= pr[i]*k)
dp[j] = max(dp[j], dp[j-pr[i]*k] + w[i]*k);
}
}
}
printf("%d\n",dp[n]);
}
return 0;
}