分组背包有关问题解法

分组背包问题解法

前面的博客中提到了0/1背包问题，下面说明一种更加复杂的动态规划问题——分组背包。

一个容量为V的背包和有N（0,1,2……i……N）件物品。第i件物品的费用是c[i]，价值是w[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。设f[k][v]表示前k组物品花费费用v能取得的最大权值，则有：
f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]|物品i属于组k}
使用一维数组的伪代码如下：
for 所有的组k
    for v=V..0 #花费从V到零，为防止重复选择同一组中的多个物品
        for 所有的i属于组k
            f[v]=max{f[v],f[v-c[i]]+w[i]}

最后的f[v]即为所求。

下面介绍一种使用分组背包的一个实例：分组背包给定 n 和 k。计算有多少长度为 k 的数组 a1, a2, ..., ak，(0≤ai) 满足：

a1 + a2 + ... + ak = n。
对于任意的 i = 0, ..., k - 1 有 ai AND ai + 1 = ai + 1。其中AND是与操作。

</pre><pre name="code" class="java">#include<iostream>
using namespace std;
#define MOD 1000000009 

int calc(int k,int n)
{
	int temp,i,j;;
	int result[10001]={0};
	int result_tem[10001]={0};
	result[0]=1;
	result_tem[0]=1;
	for(temp=1;temp<=n;temp*=2)  //表示每个二进制位
	{
		for(i=1;i<=k;i++)        //表示每个二进制位上选择1的个数
		{
			for(j=0;j<=n-temp*i;j++)  
			{
				result_tem[j+temp*i]+=result[j]; //由于每个二进制位选择1的个数只能为一个整数（多重背包和0/1背包问题）
				result_tem[j+temp*i]%=MOD;
			}
		}
		for(j=0;j<=n;j++)
			result[j]=result_tem[j];
	}	
	return result[n];
}
int main()
{
	int i,n;
	int k,m;
	cin >> n;
	for(i=0;i<n;i++)
	{
		cin >> k >> m;
		int result =calc(k,m);
		cout << result << endl;
	}
	return 0;
}

输入：

3 2

4 2

输出：

分组背包有关问题解法

相关推荐