简化版的书上背包 思路:对于以任意节点为根的子树，可以将子树按与根相连的边分组，不同组内所有的子树的可能即为有特定价值与体积的物品。要求以1为根的所有子树中含有j条枝的最大权值树，问题可以转化为从按1为根分组的所有子树中选放入体积为j的背包的所有选法的maxn，然后即可以用分组背包的思路求解,每组中可不选，选第一个，选第二个，balabalabala...【注】:分组背包问题循环遵循:(一般便于空间降维处理)for(分组)for(体积)for(决策)
AC代码
#include
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define ll long long
#define ull unsigned long long
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define per(i, l, r) for (int i = l; i >= r; --i)
#define mset(s, _) memset(s, _, sizeof(s))
#define mcpy(s, _) memcpy(s, _, sizeof(s))
#define pb push_back
#define pii pair
#define vi vector
#define vpii vector
#define mp(a, b) make_pair(a, b)
#define pll pair
#define fir first
#define sec second
#define inf 0x3f3f3f3f
inline int lowbit(int x) {return x & -x;}
template< typename T > inline void get_min(T &x, T y) {if(y < x) x = y;}
template< typename T > inline void get_max(T &x, T y) {if(x < y) x = y;}
inline int read() {
int x = 0, f = 0; char ch = getchar();
while (!isdigit(ch)) f |= ch == '-', ch = getchar();
while (isdigit(ch)) x = 10 * x + ch - '0', ch = getchar();
return f ? -x : x;
}
template
if (x < 0) putchar('-'), x = -x;
if (x >= 10) print(x / 10);
putchar(x % 10 + '0');
}
template
print(x), putchar(let);
}
const int N = 210, mod = 1e9 + 7;
int n, m;
int h[N], nex[N], v[N], w[N], idx;
void add(int a, int b, int c) {
v[idx] = b; nex[idx] = h[a]; w[idx] = c; h[a] = idx ++ ;
}
int f[N][N];
//f[i][j]:以i为根的子树中且含j条枝的所有方案的最大权值
void dp(int u, int fa) {
for(int i = h[u]; ~i; i = nex[i]) { //组别
int e = v[i];
if(e == fa) continue;
dp(e, u);
for(int j = m; j; j -- ) { //体积 此处状态表示少开了一维组别，故从大到小枚举ti'ji
for(int k = 0; k < j; k ++ ) { //决策
f[u][j] = max(f[u][j], f[u][j - k - 1] + f[e][k] + w[i]);
}
}
}
}
int main() {
mset(h, -1);
cin >> n >> m;
rep(i, 1, n - 1) {
int a, b, c; cin >> a >> b >> c;
add(a, b, c); add(b, a, c);
}
dp(1, -1);
cout << f[1][m] << endl;
return 0;
}代码转移方程说明f[u][j] = max(f[u][j], f[u][j - k - 1] + f[e][k] + w[i]);因为进行了降维处理，故max运算左边代表不选当前这组，从当前组之前的组中选的最优解，max运算右边代表选择当前这组，但因为此时还有一条与当前根相连的边要选上，故背包体积需要预留1单元，故为j - k - 1，而f[e][k]表示当前选择物品的价值