分组背包及树上分组背包

写于2016-05-04

【人生相关】好困啊QAQ 小伙伴们明天都去APIO了 当初脑残没报名= = 蛮后悔的= = 但想想2800rmb 也就还好了
美好的一天从一道树形dp开始
昨天看了下以前写的分组背包 树形dp
分组背包是说有n组物品 每个组别只能选一个 体积限制V 的最大价值w
先考虑二维：

//f[i][j] 表示 前i组体积为j的最大价值
//j k 循环可颠倒
for(int i=1;i<=N;i++) //组别
    for(int k=1;k<=n[i];k++) //每个物品
        for(int j=V;j>=0;j--) //体积
            f[i][j]=min(f[i][j],f[i-1][j-v[i][k]]+w[i]);

一维
k在j里 j倒循环 因为f[j]是由f[j-x]更新的 准确的说是f[i-1][j-x] k在里循环是要每次准确地更新出f[j]的值(k在里侧时 是没循环完一个i才准确更新出f[j]) 而j倒循环是因为每次计算f[j]时 用到的是f[i-1][j-x] 即未更新过的f[j-x] 正循环的话 都更新过了

//k在j里 j倒循环
for(int i=1;i<=N;i++) //组别
    for(int j=V;j>=0;j--) //体积
        for(int k=1;k<=n[i];k++) //每个物品
            f[j]=min(f[j],f[j-v[i][k]]+w[i]);

要我说 还有另一种写法

for(int i=1;i<=N;i++) //组别
    for(int j=V;j>=0;j--){ //体积
        for(int k=1;k<=n[i];k++) //每个物品
            f[i&1][j]=min(f[i&1][j],f[(i-1)&1][j-v[i][k]]+w[i]);
        memset(f[(i-1)&1],0,sizeof(f[(i-1)&1]));
    }

一道树(N)上分组背包 就是把每棵子树看成一个分组 每棵子树选取不同个数(or?)个节点看成每个背包中不同的物品(每个分组中只能选一个物品) 体积限制V相当于总结点数限制 这样每个节点做一次分组背包 所有节点加在一起一共有N个分组 每个组里最多有N个物品 体积限制V最多是N 时间复杂度O(N^3)
f[i&1][j]=min(f[i&1][j],f[(i-1)&1][j-v[i][k]]+w[i]);
memset(f[(i-1)&1],0,sizeof(f[(i-1)&1]));

poj2486

题目大意:求遍历k个几点权值和的最大值 (n<=200) 空间限制65536K
扶额 这么一算n^3空间是可以的啊……怎么会MLE……
好吧 改成二维的 用三维的写题解 好理解
dp[i][j][0][cnt] : i的子树走j步回到i用前cnt个分组(son)的最大权值
dp[i][j][1][cnt] : i的子树走j步不回到i用前cnt个分组(son)的最大权值
dp[i][j][0][cnt]考虑前cnt-1个点回来了且这个带你回来了dp[i][j][1][cnt]考虑成前cnt-1个点回来了第cnt个点不回来 或者 前cnt-1个点有没回来的第cnt个点回来的
还有些细节 比如 dp[i][j][0][cnt] 初始之类的
转移方程详见代码
丑的一笔

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=205;
struct E{int to,nxt;}edge[N*2];
int dp[N][N][2];
int son[N],val[N];
int idx[N],tot;
int h,n,T;
void init(){
    tot=1;
    memset(edge,0,sizeof(E));
    memset(idx,0,sizeof(idx));
    memset(dp,0,sizeof(dp));
    memset(son,0,sizeof(son));
    memset(val,0,sizeof(val));
}
void addedge(int from,int to){
    edge[tot].to=to;edge[tot].nxt=idx[from];idx[from]=tot++;
}
void dfs(int x,int fa){
    for(int t=idx[x];t;t=edge[t].nxt){
        E e=edge[t];
        if(e.to!=fa) {
            dfs(e.to,x);son[x]++;
            for(int j=h;j>=1;j--){
                dp[x][j][0]=max(dp[x][j-1][0],dp[x][j][0]);
                dp[x][j][1]=max(dp[x][j-1][1],dp[x][j][1]);
                for(int k=1;k<=j;k++){
                    if(k>=2) 
                        dp[x][j][0]=max(dp[x][j][0],dp[x][j-k][0]+dp[e.to][k-2][0]);
                    if(k>=2) 
                        dp[x][j][1]=max(dp[x][j][1],dp[x][j-k][1]+dp[e.to][k-2][0]);
                    if(k>=1) 
                        dp[x][j][1]=max(dp[x][j][1],dp[x][j-k][0]+max(dp[e.to][k-1][0],dp[e.to][k-1][1]));
                }
            }
        }
    }
}
int main(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    while(~scanf("%d%d",&n,&h)){
        init();
        int x,y;
        for(int i=1;i<=n;i++) {
            scanf("%d",&val[i]);
            for(int j=0;j<=h;j++) dp[i][j][0]=val[i];
            for(int j=1;j<=h;j++) dp[i][j][1]=val[i];
        }
        for(int i=1;i<n;i++) scanf("%d%d",&x,&y),addedge(x,y),addedge(y,x);
        dfs(1,-1);
        printf("%d\n",max(dp[1][h][1],dp[1][h][0]));
    }
    return 0;
}