【题解】luogu P1757 通天之分组背包

分组背包类型

总结：

1.先循环体积，再循环每组内的物品，保证每组物品内只选一次。

　若调换位置，有可能每组内物品多选了。

2.num数组记录每组有多少个物品；

　belong数组记录每组物品的每一个物品的序列号是多少

很巧妙的方法

#include
using namespace std;
int dp[1005], val[1005], w[1005], num[1005], belong[101][20];
int maxx, m, n, a, b, c;
int main()
{cin >> m >> n;for(int i = 1; i <= n; i++){cin >> a >> b >> c;val[i] = b;w[i] = a;maxx = max(maxx, c);num[c]++;belong[c][num[c]] = i;}for(int i = 1; i <= maxx; i++)for(int j = m; j >= 0; j--)for(int k = 1; k <= num[i]; k++)if(j >= w[belong[i][k]])dp[j] = max(dp[j], dp[j-w[belong[i][k]]]+val[belong[i][k]]);cout << dp[m];return 0;
}

转载于:https://www.cnblogs.com/lovezxy520/p/11348386.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！