上一篇講的完全背包是指在所有物品件數(shù)無限多的情況下選擇最值，現(xiàn)在引申出多重背包問題，即各物品個數(shù)w[ i ]均有限且不一定相同，且每件物品有其價值v[ i ]，求這類情況下的最值。

多重背包問題的特點是數(shù)據(jù)量大，若按照01背包的做法開dp[ m ] [ n ]的數(shù)組進行遍歷必會超時，所以建立數(shù)組時開設(shè)dp[ maxn ]（maxn為數(shù)據(jù)可能達到的最大值）。
初始化將數(shù)組dp[ ]全部設(shè)為0，將dp[ 0 ]設(shè)為1。利用雙重循環(huán) i 從1到n遍歷w[ i ]，內(nèi)層循環(huán) j 從v[ i ]開始往后遍歷，只要dp[ j - v[ i ] ]值為真（即表示價值j-v[ i ]能夠滿足）且dp[ j ]值為假（表示價值 j 尚未被滿足）則價值 j 是有可能達到的。為什么說有可能？是因為能否達到價值 j 也得看v[ i ]的數(shù)量是否達到上限。如何記錄w[ i ]的數(shù)量呢？還是要開設(shè)一個專門記錄個數(shù)的數(shù)組num[ maxn ]，在第一層循環(huán)內(nèi)將數(shù)組num[ ]初始化為0，一旦滿足 dp[ j - v[ i ] ]&&!dp[ j ]&&num[ j - v[ i ] ]<w[ i ] 則說明價值 j 是可以滿足的，則將dp[ j ]的值設(shè)為真，再將num[ j ]=num[ j - v[ i ] ]+1表示價值 j 所對應(yīng)的價值為v[ i ]的物品的使用數(shù)在價值為 j-v[ i ]的基礎(chǔ)上加1，此步操作尤為關(guān)鍵！之后根據(jù)題意看求什么邊操作即可。

特地強調(diào)！多重背包雖為背包問題的最后一篇，但其模板最好操作，幾乎百套百中！
模板：

    for(int i=1;i<=n;i++)
    {
        memset(num,0,sizeof(num));
        for(int j=v[i];j<=maxn;j++)
        {
            if(dp[j-v[i]&&!dp[j]&&num[j-v[i]]<w[i]) 
            {
                .......           //具體操作因題而異
                num[j]=num[j-v[i]]+1;  //求num[j]對應(yīng)的使用數(shù)
            }
        }
    }

典例：http://acm.hdu.edu.cn/showproblem.php?pid=2191
中文題，沒有看不懂的。
思路分析：典型的多重背包問題，開設(shè)一維數(shù)組dp[]，維數(shù)maxn便是最大價值量，之后按照上述思路雙重循環(huán)便是，dp[maxn]所對應(yīng)的便是所能買到的最大情況。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int main()
{
    int T,n,m;
    int v[105],w[105],num[105],dp[105];
    cin>>T;
    while(T--)
    {
        cin>>m>>n;
        for(int i=0;i<n;i++)
            cin>>v[i]>>w[i]>>num[i];
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;i++)
            for(int j=0;j<num[i];j++)
                for(int k=m;k>=v[i];k--)
                    dp[k]=max(dp[k],dp[k-v[i]]+w[i]);
        cout<<dp[m]<<endl;
    }
    return 0;
}

典例2：http://poj.org/problem?id=1742
題意：n種價值的硬幣，每種都有其數(shù)量w[ i ]，給一個最大價值量m求出不超過最大價值量的情況下能湊出多少種價值。
分析：這題直接按照思路模板套就行了，一套就中。

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

int use[100001];
int n,m;
bool dp[100001];
int v[1001],num[1001];
int main() 
{
    while (scanf("%d %d", &n, &m) != EOF) 
    {
        if (n == 0 && m == 0) break;
        for (int i = 0; i < n; ++i)
            scanf("%d", a+i);
        for (int i = 0; i < n; ++i) 
            scanf("%d", num+i);
        int res = 0;
        memset(dp,false,sizeof(dp));
        dp[0] = true;
        for (int i = 0; i < n; ++i) 
        {
            memset(use,0,sizeof(use));
            for (int j = a[i]; j <= m; ++j) 
            {
                if (!dp[j] && dp[j-a[i]] && use[j-a[i]]<num[i])
                {
                    dp[j] = true;
                    use[j] = use[j-a[i]] + 1;
                    ++res;
                }
            }
        }
        printf("%d\n", res);
    }
 return 0;
}