level 12
XNoZero
楼主
这样。。
问题描述：
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。
这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
解决办法：
第k组解决办法如下：
f[k][v] = max(f[k-1][v] , f[k-1][v-c[i]] + w[i])
for(int k = 0 ; k < K ; k++)
for(int v = V ; v >= 0 ; v--) //将每一个分组当做一次01背包 ,故计算顺序为V递减 for(每一个分组中的i)
f[v] = max(f[v] , f[v-c[i]] + w[i])
所谓的树形背包优化就是使用了这种方式
2011年07月18日 05点07分
1
问题描述：
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。
这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
解决办法：
第k组解决办法如下：
f[k][v] = max(f[k-1][v] , f[k-1][v-c[i]] + w[i])
for(int k = 0 ; k < K ; k++)
for(int v = V ; v >= 0 ; v--) //将每一个分组当做一次01背包 ,故计算顺序为V递减 for(每一个分组中的i)
f[v] = max(f[v] , f[v-c[i]] + w[i])
所谓的树形背包优化就是使用了这种方式