樹上背包問題

• 樹上背包問題
• • 算法原理
  • 例題一：有依賴的背包問題
  • • 題意
    • 數據范圍
    • 思路
    • 代碼
  • 例題二：二叉蘋果樹
  • • 題意
    • 數據范圍
    • 思路
    • 代碼
  • 例題三：Factories（2018icpc銀川網絡賽）
  • • 題意
    • 數據范圍
    • 思路
    • 代碼

樹上背包問題

一些題目給定了樹形結構，在這個樹形結構中選取一定數量的點或邊（也可能是其他屬性），使得某種與點權或者邊權相關的花費最大或者最小。解決這類問題，一般要考慮使用樹上背包。

算法原理

樹上背包，顧名思義，就是在樹上做背包問題。一個節點的若干子樹可以看作是若干組背包，也就是用樹形dp的方式做分組背包問題。一般來說，$f(i,j)$表示以$i$為根的子樹中，在$j$的容量范圍內，最大或者最小可以獲得多少收益。根據分組背包的思想，第一維枚舉物品（在樹上指的是子樹），第二維枚舉容量，第三維枚舉決策（這里指的是給子樹分配多少容量）?；镜拇a框架如下：

void dfs(int u, int fa) {for(int i = h[u]; ~i; i = ne[i]){int son = e[i];if(son == fa) continue;dfs(son, u);for(int j = m; j >= 0; j --)for(int k = 0; k <= j; k ++)f[u][j] = max(f[u][j], f[u][j-k] + f[son][k] + val);} }

例題一：有依賴的背包問題

題意

有$n$個物品和一個容量是$m$的背包。物品之間具有依賴關系，且依賴關系組成一棵樹的形狀。如果選擇一個物品，則必須選擇它的父節點。
求解將哪些物品裝入背包，可使物品總體積不超過背包容量，且總價值最大。輸出最大價值。
每件物品的編號是$i$，體積是$v_i$，價值是$w_i$，依賴的父節點編號是$p_i$。物品的下標范圍是$1\dots N$。

數據范圍

$1\le n,m\le 100$
$1\le v_i,w_i\le 100$

思路

$f(i,j)$表示選擇以$i$為子樹的物品，在容量不超過$j$時所獲得的最大價值。
由于只有選擇了根節點，才會繼續往下遍歷，所以在遍歷到$i$節點時，先考慮一定選上它。
在分組背包部分，$j$的范圍為$[m,v[i]]$，否則沒有意義，因為連根節點也放不下；$k$的范圍$[0,j?v[i]]$，當大于$j?v[i]$時分給該子樹的容量過多，剩余的容量連根節點的物品都放不下了。
遞推式為：$f(i,j)=max(f(i,j),f(i,j?k)+f(son,k))$。

代碼

void dfs(int u) {for(int i = v[u]; i <= m; i ++) f[u][i] = w[u];for(int i = h[u]; ~i; i = ne[i]){int son = e[i];dfs(son);for(int j = m; j >= v[u]; j --)for(int k = 0; k <= j - v[u]; k ++)f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);} }

例題二：二叉蘋果樹

題意

給定一棵二叉樹，每條邊有邊權，保留一定數量的邊（其他邊刪除），使得保留下來的邊的邊權和最大。

數據范圍

$1\le n<m\le 100$
$w_i\le 30000$

思路

$f(i,j)$表示以$i$為根的子樹中，恰好保留$j$條邊的最大邊權和。
若需要選擇該子樹中的邊，則根結點到子樹的邊一定要選，因此能用上的總邊數一定減$1$，總共可以選擇$j$條邊時，當前子樹son分配的最大邊數是$j?1$。
遞推式為，$f(i,j)=max(f(i,j),f(i,j?k?1)+f(son,k)+w[i])$。

代碼

void dfs(int u, int fa) {for(int i = h[u]; ~i; i = ne[i]){int son = e[i];if(son == fa) continue;dfs(son, u);for(int j = m; j >= 1; j -- )for(int k = 0; k <= j - 1; k ++ )f[u][j] = max(f[u][j], f[u][j - k - 1] + f[son][k] + w[i]);} }

例題三：Factories（2018icpc銀川網絡賽）

題意

給定一棵樹，邊有邊權。每個葉子節點上最多可以布置一個工廠，總共要布置$k$個工廠。問怎樣布置工廠，使得工廠之間的距離和最小。

數據范圍

$10s$
$2\le n\le 10^5$, $1\le m\le 100$
$1\le w_i\le 10^5$
多組測試數據，$n$總數不超過$10^6$

思路

直接考慮距離之和非常困難，所以可以考慮每條邊被計算了幾次（距離和等類似問題很多都是這么考慮的）。不妨設一條邊為$i$，與$i$相連的子樹中有$j$個工廠，則這條邊被計算的次數為$j?(m?j)$。
$f(i,j)$表示以$i$為根節點的子樹中，選擇恰好$j$個葉子節點的距離總和。
遞推式為，$f(i,j)=min(f(i,j),f(i,j?k)+f(son,k)+w[i]?j?(m?j))$。
因為只能分布在葉子節點，因此初始化的時候要注意，如果點$i$為葉子節點，那么$f(i,1)=0$。
同時這道題要卡常數，所以要對狀態做一個優化，即把無效狀態去掉。

代碼

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm>using namespace std;typedef long long ll;const int N = 100003, M = 103; const ll inf = 1e18;int n, m; int h[N], e[2*N], ne[2*N], w[2*N], idx; int s[N], deg[N]; ll f[N][M];void add(int a,int b,int c) {e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++; }void dfs(int u,int fa) {for(int i = h[u]; ~i; i = ne[i]){int son = e[i];if(son == fa) continue;dfs(son, u);s[u] += s[son];for(int j = min(m, s[u]); j >= 1; j --)for(int k = 1; k <= min(j, s[son]); k ++)f[u][j] = min(f[u][j], f[u][j-k] + f[son][k] + (ll)w[i] * k * (m - k));} }int main() {int T;scanf("%d", &T);int cas = 0;while(T --){scanf("%d%d", &n,&m);for(int i = 1; i <= n; i ++) h[i] = -1, deg[i] = 0;idx = 0;for(int i = 0; i < n - 1; i ++){int a,b,c;scanf("%d%d%d", &a,&b,&c);add(a,b,c), add(b,a,c);deg[a] ++, deg[b] ++;}for(int i = 1; i <= n; i ++){s[i] = 0;for(int j = 1; j <= m; j ++) f[i][j] = inf;if(deg[i]==1) f[i][1] = 0, s[i] = 1;}dfs(1, -1);printf("Case #%d: %lld\n",++cas,f[1][m]);}return 0; }

總結

以上是生活随笔為你收集整理的树上背包问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。