虽然每件物品的数目并不是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; }
