本文包含的內容：

<1> 問題描述

<2> 基本思路（和完全背包類似）

<3> 轉換為01背包問題求解（直接利用01背包）

---------------------------------------------

1、問題描述

已知:有一個容量為V的背包和N件物品，第i件物品最多有Num[i]件，每件物品的重量是weight[i]，收益是cost[i]。

問題:在不超過背包容量的情況下，最多能獲得多少價值或收益

舉例：物品個數N = 3，背包容量為V = 8，則背包可以裝下的最大價值為64.

----------------------------------------------

2、基本思路（直接擴展01背包的方程）

由于本問題和完全背包很類似，這里直接給出方程。

狀態轉移方程：

f[i][v]:表示前i件物品放入重量為v的背包獲得的最大收益
f[i][v] = max(f[i][v],f[i - 1][V - k * Weight[i]] + k * Value[i]);
其中0 <= k <= min(Num[i],V/Weight[i]);//這里和完全背包不同。
邊界條件
f[i][0] = 0;
f[v][0] = 0;

代碼：

#include <iostream>
using namespace std;
const int N = 3;//物品個數
const int V = 8;//背包容量
int Weight[N + 1] = {0,1,2,2};
int Value[N + 1] = {0,6,10,20};
int Num[N + 1] = {0,10,5,2};
int f[N + 1][V + 1] = {0};
/*
f[i][v]:表示把前i件物品放入容量為v的背包中獲得的最大收益。
f[i][v] = max(f[i - 1][v],f[i - 1][v - k * Weight[i]] + K * Value[i]);其中1 <= k <= min(Num[i],V/Weight[i])
//初始化
f[i][0] = 0;
f[0][v] = 0;
*/
int MultiKnapsack()
{
	int nCount = 0;
	//初始化
	for (int i = 0;i <= N;i++)
	{
		f[i][0] = 0;
	}
	for (int v = 0;v <= V;v++)
	{
		f[0][v] = 0;
	}
	//遞推
	for (int i = 1;i <= N;i++)
	{
		for (int v = Weight[i];v <= V;v++)
		{
			f[i][v] = 0;
			nCount = min(Num[i],v/Weight[i]);//是當前背包容量v，而不是背包的總容量
			for (int k = 0;k <= nCount;k++)
			{
				f[i][v] = max(f[i][v],f[i - 1][v - k * Weight[i]] + k * Value[i]);
			}
		}
	}
	return f[N][V];
}
int main()
{
	cout<<MultiKnapsack()<<endl;
	system("pause");
	return 1;
}

復雜度分析：

程序需要求解N*V個狀態，每一個狀態需要的時間為O（v/Weight[i]），總的復雜度為O(NV*Σ(V/Weight[i]))。

3、轉換為01背包問題求解（直接利用01背包）

思路 1、直接對每一件物品進行拆分成min（Num[i],V/Weight[i]）件，之后在拆分后的集合上進行01背包的求解。

時間復雜度：和基本思路一樣，沒有降低。

思路 2、采用二進制拆分的思想。對每i件物品，拆分的策略為：新拆分的物品的重量等于1件,2件,4件,..,(2^(k - 1)),Num[i] - (2^(k - 1))件，其中k 是滿足Num[i] - 2^k + 1 > 0 的最大整數。

注意，

（1）最后一個物品的件數的求法和前面不同，其直接等于 該物品的最大件數 - 前面已經分配之和。

（2）分成的這幾件物品的系數和為

Num[i]，表明第i種物品取的件數不能多于Num[i]。

舉例：某物品為13件，則其可以分成四件物品，其系數為1,2,4,6.這里k = 3。

當然，這里使用二進制的前提還是使用二進制拆分能

保證對于0,,,Num[i]間的每一個整數，均可以用若干個系數的和表示。

具體使用時，有一個小優化，即：

我們不對所有的物品進行拆分，因此物品一旦拆分，其物品個數肯定增加，那么復雜度肯定上去。

此時，我們可以選擇性地對物品進行拆分：

（1）如果第i個物品的重量Weight[i] * 物品的個數Num[i] >= 背包總重量V，可以不用拆分。

（2）如果第i個物品的重量Weight[i] * 物品的個數Num[i] < 背包總重量V，可以不用拆分。

其實，拆不拆分，就看該物品能不能滿足完全背包的條件。即，看該物品能不能無限量供應。

解釋：為啥滿足Weight[i] * 物品的個數Num[i] >= 背包總重量V的物品可以不用拆分?

此時，滿足該條件時，此物品原則上是無限供應，直到背包放不下為止。

最終，對于不需要拆分的物品，可以看出完全背包的情況，調用處理完全背包物品的函數。對于需要拆分的物品，可以看出01背包的情況，調用處理01背包物品的函數。

這樣，由于不對滿足完全背包的物品進行拆分，此時物品個數就沒有對所有物品拆分時的物品個數多，即程序中外層循環降低，復雜度也就下去了。

偽代碼：

這里：C表示該物品的重量。M表示該物品的個數。V表示背包的最大容量。W表示該物品的收益。

代碼：