標簽：依賴 bsp i++ col class tor span res 背包問題
據傳這類問題叫做有依賴性的背包問題：
選某個物品的同時必須連帶選其他物品
容易想到其實是決策發生了變化：
可以選啥都不選
可以只選主件
可以選主件+一個附件
可以選主件+兩個附件
其他和01背包一樣
struct Bag { int w; int val; Bag(int x = 0,int y = 0) : w(x),val(y){} }; vector<Bag> a[65]; Bag s[65]; int vis[65]; int dp[32005]; int main() { int n, m; int x, y, z; n = readint(), m = readint(); for (int i = 0; i < m; i++) { x = readint(), y = readint(), z = readint(); if (!z) s[i].val = y, s[i].w = x; else a[z - 1].push_back(Bag(x, y)), vis[i] = -1; } for (int i = 0; i < m; i++) { if (vis[i] == -1) continue; for (int j = n; j >= s[i].w; j--) { int res = dp[j]; res = max(res, dp[j - s[i].w] + s[i].val * s[i].w); if (!a[i].empty()) { if (j - s[i].w - a[i][0].w >= 0) res = max(res, dp[j - s[i].w - a[i][0].w] + s[i].val * s[i].w + a[i][0].val * a[i][0].w); if (a[i].size() > 1) { if (j - s[i].w - a[i][1].w >= 0) res = max(res, dp[j - s[i].w - a[i][1].w] + a[i][1].val * a[i][1].w + s[i].val * s[i].w); if (j - s[i].w - a[i][0].w - a[i][1].w >= 0) res = max(res, dp[j - s[i].w - a[i][0].w - a[i][1].w] + s[i].val*s[i].w + a[i][0].val * a[i][0].w+ a[i][1].w * a[i][1].val); } } dp[j] = res; } } Put(dp[n]); }
標簽：依賴 bsp i++ col class tor span res 背包問題
原文地址：https://www.cnblogs.com/hznumqf/p/13405970.html
