Description

Input

Output

Sample Input

3 10

1 2 4 2 1 1

2 5

1 4 2 1

0 0

Sample Output

8

4

多重背包, 可惜一般多重背包解法不可用

Q: 第二层循环到底是 v 还是余数 d ?

A: 严格分组背包问题的第二层循环是 d, 但也并非完全如此, 第二层分了3个部分, 分别是 01背包, 完全背包, 严格分组背包三种情况

思路:

1. 使用 DP 单调队列求解

2. 分析背包问题的一般解法, 并寻找优化方案

3. 背包问题一般解法的动态规划方程为 dp[i][v] = max(dp[i-1][v-k*w[i]]+k*v[i])

4. 将(3)写的再详细一点, 就是 dp[i][v] = max(dp[i-1][v](不拿), dp[i-1][v-w[i]]+v[i](拿一件), ... dp[i-1][v-k*w[i]]+k*v[i]), 假设 k 是允许拿的最多件数. 关于 k 的取值范围, 首先, k 应该小于 n[i](即第 i 件物品的件数), 其次, k*w[i] < v

5. 举个例子, 对于第 i 件物品, 假设 k == 2, 同时 v 恰好等于 6*w[i], 那么

　　dp[i][6*w[i]] = max(dp[i-1][6*w[i]], dp[i-1][5*w[i]]+v[i], dp[i-1][4*w[i]]+2*v[i])

　　dp[i][5*w[i]] = max(dp[i-1][5*w[i]], dp[i-1][4*w[i]]+v[i], dp[i-1][3*w[i]]+2*v[i])

　　dp[i][4*w[i]] = max(dp[i-1][4*w[i]], dp[i-1][3*w[i]]+v[i], dp[i-1][2*w[i]]+2*v[i])

观察上面三个式子, 发现等号右边有重复的部分, 比如 dp[i-1][4*w[i]] 在三个式子中都出现过, 那么对上式做一下调整

　　第一个式子, 右边都减去 6*v[i]

　　dp[i][6*w[i]] = max(dp[i-1][6*w[i]]-6*v[i], dp[i-1][5*w[i]]-5*v[i], dp[i-1][4*w[i]]-4*v[i]) + 6*v[i]

　　第二个式子, 等号右边减去 5*v[i]

　　dp[i][5*w[i]] = max(dp[i-1][5*w[i]]-5*v[i], dp[i-1][4*w[i]]-4*v[i], dp[i-1][3*w[i]]-3*v[i]) + 5*v[i]

　　第三个式子, 等号右边减去 4*v[i]

　　dp[i][4*w[i]] = max(dp[i-1][4*w[i]], dp[i-1][3*w[i]]-3*v[i], dp[i-1][2*w[i]]+2*v[i]) + 4*v[i]

经过转化, 三个式子右边就出现了部分相同的式子, 相同就意味着可以减少重复计算, 那么, 计算 dp[i][v] 的时候, 可以使用单调队列减少冗余计算, 比如

　　开始时, 队列含有 dp[i][4*w[i]] 等号右边三个子式, 求解完 dp[i][4*w[i]], 压缩唯一一个新的子式 dp[i-1][5*w[i]]-5*v[i], 并挤掉 dp[i-1][2*w[i]]+2*v[i], 最后压入 dp[i-1][6*w[i]]-6*v[i], 挤掉 dp[i-1][3*w[i]]-3*v[i], 单调队列能使这个过程的复杂度为 o(1) (dp[i-1][k*w[i]+d] 进入单调队列的次数仅有一次)

6. 再具体一些. v==k*w[i] 的意思是背包的容量恰好是第 i 件物品的 k 倍, 此时 d = v%w[i] = 0. 当 v == k*w[i]+1 时, 即 d == 1, 那么一次遍历可以求解 dp[i][6*w[i]+1], dp[5*w[i]+1], dp[i][4*w[i]]+1]... 可见, 每次遍历能够求解余数相同的那些数

假设 d == v%w[i], d 的取值范围是 [0, w[i]) , 每一项减去的是 v/w[i]

程序的框架可以是

7. 当 w == v 时的一个特例

每次入队(新加入队列)中的元素是 f[v]-(v/w[i])*v[i], 因为 w==v, 那么 f[v]-v+d, 其中 d=v%w[i]

返回的最大值是 队首元素+k/w[i]*v[i] = 队首元素+k-d

针对 1742 这道题, 题目仅要求求解能够覆盖的那些值, 所以题目变得简单一些了

对于 dp[i][k*w[i]+d], 我们仅需判断 dp[i][(k-(0...n[i]))*w[i]+d] 是否有 1  即可, 这有简化为 dp[i][(k-(0...n[i]))*w[i]+d] 的和是否为 0. 不为 0, 则覆盖

总结:

1. 多重背包的一般解法

　　<1> 直接解法. dp[i][v] = max(dp[i-1][v-k*w[i]]+k*v[i])

　　<2> 转换成01背包. 将一种物品拆分成 1, 2, 4, ...N-2^k-1件. 比如 13就能拆分成 1, 2, 4, 6 件, 然后使用 01 背包的思路求解

2. 单调队列的初始化方法

　　<1> st初始化为0, ed 初始化为 -1

　　<2> queue[++ed] = dp[v]

　　可以减少判断

3. 第 29 行代码 WA 过, v = d, 而不是 v =w[i]

代码:

#include <iostream>

using namespace std;

const int MAXN = 150;

int w[MAXN], c[MAXN];

int n, m;

bool dp[100000+10], queue[100000+10];

int solve_dp() {

	memset(dp, 0, sizeof(dp));

	memset(queue, 0, sizeof(queue));

	dp[0] = true;

	for(int i = 0; i < n; i ++) {

		if(c[i] == 1) {		// 仅允许一个包, 变成01背包问题

			for(int v = m; v >= w[i]; v--) {

				if(!dp[v] && dp[v-w[i]])

					dp[v] = 1;

			}

		}else if(c[i]*w[i] >= m) {	// 完全背包问题, 即 w[i]*c[i] < m, 放入件数的限制是 c[i]

			for(int v = w[i]; v <= m; v++) {

				if(!dp[v] && dp[v-w[i]])

					dp[v] = 1;

			}

		}else{	// 严格的分组背包问题

			for(int d = 0; d < w[i]; d++) {		// 对于所有余数 d [0, w[i])

				// 窗口大小为 c[i]

				int sum = 0, st = 0, ed = -1;	//st,ed 单调队列的开始和结尾, sum 队列中是否有一个 true

				for(int v = d; v <= m; v+= w[i]) {	// 完全背包 model, 但步长是 w[i]

					if(ed - st == c[i]) {	// 窗口大小为0, 移除队首元素, 队首后移一位

						sum -= queue[st++];

					}

					queue[++ed] = dp[v];

					sum += dp[v];

					if(!dp[v] && sum)

						dp[v] = 1;

				}

			}

		}

	}

	int res = 0;

	for(int i = 1; i <= m; i ++)

		res += dp[i];

	return res;

}

int main() {

	freopen("E:\\Copy\\ACM\\测试用例\\in.txt", "r", stdin);

	while(cin >> n >> m && n != 0) {

		for(int i = 0; i < n; i ++) {

			scanf("%d", &w[i]);

		}

		for(int i = 0; i < n; i ++) {

			scanf("%d", &c[i]);

		}

		// main function

		cout << solve_dp() << endl;

	}

	return 0;

}

Update: 2014年3月14日10:04:41

1. sum = 1 -> dp[v] = 1 优化非常巧妙, 第二次做时依然没想到

2. 分组背包时, 注释写了完全背包 model, 但实际上写成 01 背包 model 也是可以的, 结果与之无关. 但写成 01 背包 model 更加合适, 毕竟分组背包的经典解法是转化为 01 背包

3. 此题和 九度 买卖股票 可以很好做下对比

4. 楼天成是男人就做八题其中一道