传送门
用分组背包策略解决
不知道为什么下面自己写的代码全部数据都过不了。。。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define INF 0x3f3f3f3f
#define N 61using namespace std;int main()
{int n, m;int w[N][3]={0};int v[N][3]={0};int f[N] ={0};int dp[32001]={0};int a, b, c;scanf("%d%d", &n, &m);for(int i=1; i<=m; i++) {scanf("%d%d%d", &a, &b, &c);if(c) {f[c]++;w[c][f[c]] = a;v[c][f[c]] = a*b;}else {w[i][0] = a;v[i][0] = a*b;}}for(int i=1; i<=m; i++) {for(int j=n; j>=w[i][0]&&w[i][0]!=0; j--) {//只买主件dp[j] = max(dp[j], dp[j-w[i][0]]+v[i][0]);// 买主件和一件附件if(j>= w[i][0]+w[i][1])dp[j] = max(dp[j], dp[j-w[i][1]-w[i][1]]+v[i][1]+v[i][1]);if(j>= w[i][0]+w[i][2])dp[j] = max(dp[j], dp[j-w[i][2]-w[i][2]]+v[i][2]+v[i][2]);if(j>=w[i][0]+w[i][1]+w[i][2])dp[j] = max(dp[j], dp[j-w[i][0]-w[i][1]-w[i][2]]+v[i][0]+v[i][1]+v[i][2]);}}printf("%d\n", dp[n]);return 0;
}