分組背包類型

總結(jié)：

1.先循環(huán)體積，再循環(huán)每組內(nèi)的物品，保證每組物品內(nèi)只選一次。

　若調(diào)換位置，有可能每組內(nèi)物品多選了。

2.num數(shù)組記錄每組有多少個(gè)物品；

　belong數(shù)組記錄每組物品的每一個(gè)物品的序列號(hào)是多少

很巧妙的方法

#include<bits/stdc++.h> 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; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/lovezxy520/p/11348386.html

總結(jié)

以上是生活随笔為你收集整理的【题解】luogu P1757 通天之分组背包的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。