多重背包也是一种基本的背包问题模型，其基本特点是：每种物品有一个固定的装入次数上限。

        多重背包问题的一般描述为：有N个物品，第i个物品的重量与价值分别为W[i]与P[i]且第i种物品最多有C[i] 件。背包容量为V，试问在每个物品不超过其上限的件数（物品必须保持完整）的情况下，如何让背包装入的物品具有更大的价值总和。

        其一般解题思路为：

        设f[i][j] 表示从编号1~i的物品中挑选任意数量的任意物品放入容量为j的背包中得到的最大价值，那么有  f[i][j]=max { f[i−1][j−k∗w[i]]+k∗v[i] ∣0≤k≤p[i]&k∗w[i]≤j }。

编写代码时，可以写成如下的循环。

    for  ( i = 1; i <= N; i++)

         for  ( j = 1; j <= V; j++)

             for  (k = 0;  k <= C[i] &&  k * W[i] <= j; k++)

            {

                  f[i][j] = max( f[i][j], f[i - 1][j - k * W[i]] + k *P[i]);

             }

求得的最优值为f[N][V]。

        同样多重背包也可以进行空间优化，将二维数组优化为一维数组，即

              f[j]=max { f[j]，f[j−k∗W[i]]+k∗P[i] }  （0≤k && k∗W[i]≤j）

编写代码时，一般采用如下的循环。

    for (i=1; i<=N; i++)

       for (j=V; j>=0; j--)  

          for (k=0; k<=c[i] &&  k*W[i] <=j; k++)

              f[j] = max( f[j], f[j - k * W[i]] + k *P[i]);

求得的最优值为f[V]。

        从上面的程序代码可以看出，多重背包的处理一般采用三重循环，时间复杂度较高。为了对时间进行优化，可以采用二进制优化法将多重背包转变为0/1背包（采用二重循环）进行处理。

        所谓二进制优化法就是将第 i 种c[i]件物品按二进制的方法分拆成s份“不同”的物品。例如，设第i件物品有20件，每件重量和价值分别为w和p，则可以分拆别5份“物品”如下：

第1份含有1件物品，重量为w，价值为p；

第2份含有2件物品，重量为2w，价值为2p；

第3份含有4件物品，重量为4w，价值为4p；

第4份含有8件物品，重量为8w，价值为8p；

第5份含有5件物品，重量为5w，价值为5p。

        因为，1+2+4+8+5=20，则由这5份“物品”可组合成0~20件之间任意件数的物品。这5份“物品”在进行组合时，每份物品要么选取，要么不选取，正好就是对这5份物品进行0/1背包处理。由此，多重背包可以通过这种方式转化为0/1背包进行处理。从而将三重循环优化为二重循环处理。

        我们知道，k位二进制数可以表示0~2^k-1之间的任意整数，k位二进制数从低位到高位，各位上的权值依次为1（2⁰）、2（2¹）、4（2²）、…、2^k-1。因此，对于任意一个正整数x，则可以将其拆分为1+2+4+…+2^k-1+y（其中y是二进制拆分剩余的部分，y<2^k）。

        通过拆分后，就可以将多重背包问题转换为0/1背包问题求解了。

编写代码如下：

         for (i=1; i<=N; i++)

        {

            int  s =C[i];

            for  (j=1; j<=s;  s-=j, j=j*2)                       // 二进制拆分

            {

                for  (k =V; k >=0 && k>= j*W[i]; k--)   // 0/1背包

                {

                    f[k] = max(f[k], f[k - j*W[i]] + j *P[i]);

                }

            }

            if (s > 0)                                               // 拆分的剩余部分

            {

                 for  ( j =V; j >= s * W[i]; j--)

                 {

                    f[j] = max(f[j], f[j - s * W[i]] + s * P[i]);

                 }

            }

        }

 【例1】购买粮食

问题描述

你准备自己采购一些粮食支援灾区，现在假设你一共有资金n元，而市场有m种大米，每种大米都是袋装产品，其重量和价格不等，并且只能整袋购买。

请问：你用有限的资金最多能采购多少公斤粮食呢？

输入

输入数据首先包含一个正整数C，表示有C组测试用例，每组测试用例的第一行是两个整数n和m（1<=n<=100，1<=m<=100），分别表示经费的金额和大米的种类，然后是m行数据，每行包含3个数p，h和c（1<=p<=20,1<=h<=200,1<=c<=20），分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。

输出

对于每组测试数据，请输出能够购买大米的最多重量，你可以假设经费买不光所有的大米，并且经费你可以不用完。每个实例的输出占一行。

输入样例

1

8 2

2 100 4

4 100 2

输出样例

400

          （1）编程思路。

         典型的多重背包问题。按上面介绍的方法，采用二维数组编写源程序1；采用一维数组编写源程序2；采用二进制优化的方法编写源程序3。

         （2）采用二维数组编写的源程序1。

#include <stdio.h>
#include <string.h>
int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    int p[105],h[105],c[105],f[105][105];
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        int i,j,k;
        for (i=1;i<=m;i++)
            scanf("%d%d%d",&p[i],&h[i],&c[i]);
        memset(f,0,sizeof(f));
        for (i=1;i<=m;i++)
           for (j=1; j<=n; j++)
              for (k=0; k<=c[i] &&  k*p[i] <=j; k++)
                 f[i][j]=max(f[i][j],f[i-1][j-k*p[i]]+k*h[i]);
        printf("%d\n",f[m][n]);
    }
    return 0;
}

         （3）采用一维数组编写的源程序2。

#include <stdio.h>
#include <string.h>
int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    int p[105],h[105],c[105],f[105];
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        int i,j,k;
        for (i=1;i<=m;i++)
            scanf("%d%d%d",&p[i],&h[i],&c[i]);
        memset(f,0,sizeof(f));
        for (i=1;i<=m;i++)
            for (j=n;j>=0;j--)
                 for (k=0; k<=c[i] &&  k*p[i] <=j; k++)
                    f[j]=max(f[j],f[j-k*p[i]]+k*h[i]);
        printf("%d\n",f[n]);
    }
    return 0;
}

        （4）采用二进制优化的方法编写的源程序3。

#include <stdio.h>
#include <string.h>
int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    int p[105],h[105],c[105],f[105];
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        int i,j,k;
        for (i=1;i<=m;i++)
            scanf("%d%d%d",&p[i],&h[i],&c[i]);
        memset(f,0,sizeof(f));
        for (i=1; i<=m; i++)
        {
            int  s =c[i];
            for  (j=1; j<=s;  s-=j, j=j*2)    // 二进制拆分
            {
                for  (k =n; k >=0 && k>= j*p[i]; k--)  // 0/1背包
                {
                    f[k] = max(f[k], f[k - j*p[i]] + j *h[i]);
                }
            }
            if (s > 0)          // 拆分的剩余部分
            {
                 for  ( j =n; j >= s * p[i]; j--)
                 {
                    f[j] = max(f[j], f[j - s * p[i]] + s * h[i]);
                 }
            }
        }
        printf("%d\n",f[n]);
    }
    return 0;
}

【例2】摆花

问题描述

小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共m盆。通过调查顾客的喜好，小明列出了顾客最喜欢的n种花，从1到n标号。为了在门口展出更多种花，规定第i种花不能超过 ai盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。

试编程计算，一共有多少种不同的摆花方案。

输入

第一行包含两个正整数n和m（0<n≤100，0<m≤100），中间用一个空格隔开。

第二行有n个整数，每两个整数之间用一个空格隔开，依次表示 a1,a2,…,an。

输出

一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出方案数对 10^6+7取模的结果。

输入样例

2 4

3 2

输出样例

2

         （1）编程思路。

        典型的多重背包问题。按前面的介绍进行处理即可。

        采用二维数组，定义int f[105][105]={0}。设f[i][j]表示前i种花中摆放j盆花的方案数，初始值初f[0][0]=1（什么也不摆）外，其余全部为0。可以编写如下的源程序1。

        采用一维数组，int f[105]={0}；设f[i]表示摆放i盆花的方案数。可以编写如下的源程序2。

        （2）使用二维数组编写的源程序1。

#include <stdio.h>
int main()
{
    int f[105][105]={0},a[105];
    int n,m;
    scanf("%d%d",&n,&m);
    int i,j,k;
    for (i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
    }
    f[0][0]=1;
    for (i=1; i<=n; i++)
       for (j=0; j<=m; j++)
          for (k=0; k<=(a[i]<j?a[i]:j); k++)
              f[i][j] = (f[i][j] + f[i-1][j-k])%1000007;
    printf("%d\n",f[n][m]);
    return 0;
}

         （3）使用一维数组编写的源程序2。

#include <stdio.h>
int main()
{
    int f[105]={0},a[105];
    int n,m;
    scanf("%d%d",&n,&m);
    int i,j,k;
    for (i=1; i<=n; i++)
        scanf("%d",&a[i]);
    f[0] = 1;
    for (i=1; i<=n; i++)
       for (j=m; j>=0; j--)
          for (k=1; k<=(a[i]<j?a[i]:j); k++)
              f[j] = (f[j] + f[j-k])%1000007;
    printf("%d\n",f[m]);
    return 0;
}

        将上面的源程序1和2提交给洛谷题库P1077 [NOIP2012 普及组] 摆花（https://www.luogu.com.cn/problem/P1077），测评结果均为“Accepted”。

 【例3】收集樱花

问题描述

有k棵樱花树，在第i棵树下最多能收集到 si朵樱花（收集了0朵樱花也算收集了樱花）。

你有多少种方案能够收集到恰好n朵樱花呢？

输入

第一行两个正整数 n,k，表示要收集n朵樱花，有k棵樱花树。

接下来一行k个正整数 s1,s2,…,sk，其中 si表示最多在第i棵樱花树下收集到si朵樱花。

输出

一行一个整数，表示恰好收集到n朵樱花的方案数。

由于答案可能太大，请输出答案对 10086001 取模后的值。

特殊地，如果收集不到n朵樱花，请输出一个字符串 impossible。

输入样例#1

3 4

1 1 1 1

输出样例 #1

5

输入样例 #2

10 9

9 6 8 7 9 6 5 4 3

输出样例#2

68345

输入样例 #3

10 5

2 2 2 2 1

输出样例 #3

Impossible

        （1）编程思路1。

        定义二维数组int f[5001][5001]；其中f[i][j]表示前i颗樱花树下共收集到j朵樱花的方案数。显然，有f[i][0]=1（1≤i≤n，每颗树下可不收集樱花，收集了0朵樱花也算收集了樱花，方案数为1），还有f[1][j]=1（1≤j≤s[1]，第1颗樱花树下可分别收集1~s[1]朵樱花）。

        转移方程为： f[i][j]=f[i][j]+f[i-1][j-k]  （其中k值为第i可樱花树收集樱花的朵数）。

        （2）源程序1。

#include <stdio.h>
#include <string.h>
int f[5001][5001]={0};
int main()
{
    int v,n;
    scanf("%d%d",&v,&n);
    int s[5001];
    int i,j,k;
    int tot=0;
    for (i=1;i<=n;i++)
    {
        scanf("%d",&s[i]);
        tot+=s[i];
    }
    if (tot<v)
    {
        printf("impossible\n");
        return 0;
    }
    for (i=1;i<=n;i++)
        f[i][0]=1;
    for (i=1;i<=s[1];i++)
        f[1][i]=1;
    for (i=2; i<=n; i++)
    {
        for (j=1; j<=v; j++)
        {
             for  (k=0;  k<=s[i] &&  k<=j; k++)
             {
                  f[i][j]=(f[i][j]+f[i-1][j-k])%10086001;
             }
        }
    }
    int ans=0;
    for (i=1; i<=n; i++)
        ans = (ans+f[i][v])%10086001;
    printf("%d\n",ans);
    return 0;
}

        将上面的源程序1提交给洛谷题库P6394 樱花，还有你（https://www.luogu.com.cn/problem/P6394），测评结果为“Unaccepted”，其中测试点#17、测试点#19和测试点#20，显示“TLE”，测试点#18显示“MLE”。

         （3）编程思路2。

        由于数据量较大，因此采用二维数组存储，会存在超内存限制的情况，因此采用一维数组进行处理。

        （4）源程序2。

#include <stdio.h>
#include <string.h>
int f[5001]={0};
int main()
{
    int v,n;
    scanf("%d%d",&v,&n);
    int s[5001];
    int i,j,k;
    int tot=0;
    for (i=1;i<=n;i++)
    {
        scanf("%d",&s[i]);
        tot+=s[i];
    }
    if (tot<v)
    {
        printf("impossible\n");
        return 0;
    }
    f[0]=1;
    int ans=0;
    for (i=1;i<=n;i++)        //  前i棵树
    {
        for (j=v;j>=0;j--)   
            for (k=1;k<=s[i] && k<=j;k++)
                 f[j]=(f[j]+f[j-k])%10086001;
        ans=(ans+f[v])%10086001;
    }
    printf("%d\n",ans);
    return 0;
}

        将上面的源程序2提交给洛谷题库P6394 樱花，还有你（https://www.luogu.com.cn/problem/P6394），测评结果仍为“Unaccepted”，其中测试点#17、测试点#18、测试点#19和测试点#20，均显示“TLE”。

        （5）编程思路3。

         源程序2中的多重背包采用三重循环实现，由于数据量较大，循环处理太耗时，因此会超时。观察第三层循环，每次的f[j]都是加上一个区间，所以可以直接用一个前缀和来计算，这样第三层循环就可以省掉了。

        （6）源程序3。

#include <stdio.h>
int main()
{
    int v,n;
    scanf("%d%d",&v,&n);
    int f[5001]={0};
    int s[5001];
    int sum[5001]={0};  // 保存前缀和
    int i,j;
    int tot=0;
    for (i=1;i<=n;i++)
    {
        scanf("%d",&s[i]);
        tot+=s[i];
    }
    if (tot<v)
    {
        printf("impossible\n");
        return 0;
    }
    sum[0]=f[0]=1;
    int ans=0;
    for (i=1;i<=n;i++)        // 前i棵树
    {
        for (j=1;j<=v;j++)    // 更新前缀和
           sum[j]=(sum[j-1]+f[j])% 10086001;
        for (j=v;j>=1;j--)   
        {
            int k=s[i]<j?s[i]:j;
            if (k==j) f[j]=(f[j]+sum[j-1])% 10086001;
            else f[j]=(f[j]+sum[j-1]-sum[j-k-1]+10086001)% 10086001;  //利用前缀和
        }
        ans=(ans+f[v])%10086001;
    }
    printf("%d\n",ans);
    return 0;
}

        将上面的源程序3提交给洛谷题库P6394 樱花，还有你（https://www.luogu.com.cn/problem/P6394），测评结果为“Accepted”。

 【例4】砝码称重

问题描述

设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重≤1000），计算用这些砝码能称出的不同重量的个数N，但不包括一个砝码也不用的情况。

输入

输入方式：a1 , a2 ,a3 , a4 , a5 ,a6（表示1g砝码有a1个，2g砝码有a2个，…，20g砝码有a6个）。

输出

输出方式：Total=N

输入样例

1 1 0 0 0 0

输出样例

Total=3

          （1）编程思路。

         设f[i]表示重量i是否可以称出。初始时，f[0]=1，其余全部为0。输入6种砝码的个数w[i]，计算出所有砝码全部使用时，可称出的总重量tot，这也是背包的容量。

        将6种砝码按多重背包的处理方法加入背包，若重量j-w[i]*k可称出，即f[j-w[i]*k]==1，则加上k个重w[i]的砝码后，重量j也可以称出，置f[j]=1。

        多重背包处理完后，f[1]~f[tot]元素值为1的个数就是可称出的不同重量的个数。

        （2）源程序。

#include <stdio.h>
int main()
{
    int f[1001]={0};
    int w[7]={0,1,2,3,5,10,20};
    int a[7];
    int i,j,k;
    int tot=0;   // 总重量
    for (i=1;i<=6;i++)
    {
        scanf("%d",&a[i]);
        tot+=w[i]*a[i];
    }
    f[0]=1;
    for (i=1;i<=6;i++)
    {
          for (j=tot;j>=0;j--)
              for (k=0;k<=a[i];k++)
              {
                   if (j-w[i]*k>=0 && f[j-w[i]*k]!=0)
                    f[j]=1;
            }
    }
    int ans=0;
    for (i=1;i<=tot;i++)
       if (f[i]!=0) ans++;
    printf("Total=%d\n",ans);
  return 0;
}

        将上面的源程序提交给洛谷题库P2347 [NOIP1996 提高组] 砝码称重（https://www.luogu.com.cn/problem/P2347），测评结果为“Accepted”。

 【例5】买表

问题描述

Jimmy 到 Symbol 的手表店买手表，Jimmy 只带了n种钱币，第i种钱币的面额为 ki元，张数为 ai张。Symbol 的店里一共有m 块手表，第i 块手表的价格为 ti元。

Symbol 的手表店不能找零，所以 Jimmy 只能在凑出恰好的钱数时才能购买一块手表。现在对于店里的每块手表，Jimmy 想知道他能不能凑出恰好的钱数进行购买。

输入

第一行两个空格分隔的整数 n（1≤n≤200）和 m（1≤m≤100000） 表示钱币数与手表数。

接下来 n 行每行两个空格分隔的整数 ki（1≤ki≤500000）和 ai（1≤ai≤1000）表示钱币的面额和张数。

第 n+2行，共 m个用空格分隔的整数 ti（0≤ti≤500000），表示每块手表的价格。

输出

一共m 行，对于第i 行，如果能凑出恰好的钱数购买第i 块手表则输出 Yes 否则输出 No，注意只有首字母大写。

输入样例

3 5

1 2

5 1

6 3

3 19 21 1 7

输出样例

No

Yes

No

Yes

Yes

         （1）编程思路。

        设f[i]表示钱数i是否可以用n种钱币凑出。初始时，f[0]=1，其余全部为0。由于每种钱币的张数较多（最多可达1000张），因此按照前面介绍的二进制数优化方法，将多重背包变化成0/1背包进行处理。

        （2）源程序。

#include <stdio.h>
#include <string.h>
int main()
{
    int f[500005]={0},w[2005];
    int n,m;
    scanf("%d%d",&n,&m);
    int i,j;
    int cnt=0;
    for (i=1; i<=n; i++)
    {
        int k,a;
        scanf("%d%d",&k,&a);
        for (j=1; j<=a; j*=2)  // 多重背包转成0/1背包
        {
            w[++cnt]=j*k;
            a-=j;
        }
        if (a>0)
        {
            w[++cnt]=k*a;
        }
    }
    f[0]=1;
    for (i=1; i<=cnt; i++)      // 01背包的求解
        for(j=500000; j>=w[i]; j--)
            if (f[j-w[i]]) f[j]=1;
    for (i=1;i<=m;i++)
    {
        int t;
        scanf("%d",&t);
        if (f[t]) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

        将上面的源程序提交给洛谷题库P6567 [NOI Online #3 入门组] 买表（https://www.luogu.com.cn/problem/P1776），测评结果为“Accepted”。

 【例6】英雄联盟

问题描述

正在上大学的小皮球热爱英雄联盟这款游戏，而且打的很菜，被网友们戏称为「小学生」。

现在，小皮球终于受不了网友们的嘲讽，决定变强了，他变强的方法就是：买皮肤！

小皮球只会玩N个（5≤N≤150）英雄，因此，他也只准备给这N个英雄买皮肤，并且决定，以后只玩有皮肤的英雄。

这N个英雄中，第i个英雄有Ki 款皮肤，价格是每款 Ci个Q 币（同一个英雄的皮肤价格相同）。

为了让自己看起来高大上一些，小皮球决定给同学们展示一下自己的皮肤，展示的思路是这样的：对于有皮肤的每一个英雄，随便选一个皮肤给同学看。

比如，小皮球共有 5 个英雄，这 5 个英雄分别有0,0,3,2,4 款皮肤，那么，小皮球就有3×2×4=24 种展示的策略。

现在，小皮球希望自己的展示策略能够至少达到M （M≤10¹⁷）种，请问，小皮球至少要花多少钱呢？

输入

第一行，两个整数N,M。

第二行，N个整数，表示每个英雄的皮肤数量Ki。

第三行，N 个整数，表示每个英雄皮肤的价格Ci 。

输出

一个整数，表示小皮球达到目标最少的花费。

输入样例

3 24

4 4 4

2 2 2

输出样例

18

         （1）编程思路。

         展示方案达到M种作为背包的容量，每一个英雄都有一个皮肤数量、一个购买的Q币数（花费），将每个英雄的皮肤看成物品，就是有限物品数量的多重背包问题。

         设f[j]表示花费j个Q币购买英雄皮肤可得到的最大展示方案数量，则状态转移方程为：

         f[j]=max(f[j−p∗c[i]]∗p,f[j])，其中 p是当前英雄所选的皮肤数量，c[i]该皮肤的购买价格。

         多重背包处理完后，用变量i从0~tot搜索f[i]的判断，第1次遇到的 f[i]>=m的i值就是所求的最小花费。

          （2）源程序。

#include <stdio.h>
long long max(long long a,long long b)
{
    return a>b?a:b;
}
long long f[250000]={0};
int main()
{
    int n;
    long long m;
    scanf("%d%lld",&n,&m);
    int i,j,p;
    int k[155],c[155];
    for (i=1;i<=n;i++)
        scanf("%d",&k[i]);
    int tot=0;   // 花的总钱数
    for (i=1;i<=n;i++)
    {
        scanf("%d",&c[i]);
        tot+=c[i]*k[i];
    }
    f[0]=1;
    for (i=1;i<=n;i++)
    {
          for (j=tot;j>=0;j--)
              for (p=0;p<=k[i];p++)
              {
                   if (j-c[i]*p>=0)
                    f[j]=max(f[j],1L*f[j-c[i]*p]*p);
            }
  }
  for (i=0;i<=tot;i++)
    if (f[i]>=m)
    {
       printf("%d\n",i);
       break;
    }
  return 0;
}

         将上面的源程序提交给洛谷题库P5365 [SNOI2017]英雄联盟（https://www.luogu.com.cn/problem/P5365），测评结果为“Accepted”。

 【例7】宝物筛选

问题描述

小F找到了王室的宝物库，里面堆满了无数价值连城的宝物。但是这里的宝物实在是太多了，小F的采集车似乎装不下那么多宝物。看来小F只能含泪舍弃其中的一部分宝物了。

小F对库里的宝物进行了整理，他发现每样宝物都有一件或者多件。他粗略估算了下每样宝物的价值，之后开始了宝物筛选工作：小F有一个最大载重为W的采集车，宝物库里总共有n种宝物，每种宝物的价值为vi，重量为wi，每种宝物有mi件。小F希望在采集车不超载的前提下，选择一些宝物装进采集车，使得它们的价值和最大。

输入

第一行为一个整数n（1≤n≤100）和W（0≤W≤40000），分别表示宝物种数和采集车的最大载重。

接下来n行每行三个整数vi,wi,mi。n≤∑mi ≤100000。

输出

输出仅一个整数，表示在采集车不超载的情况下收集的宝物的最大价值。

输入样例

4 20

3 9 3

5 9 1

9 4 2

8 1 3

输出样例

47

         （1）编程思路1。

        典型的多重背包问题，按前面介绍的采用一维数组用三重循环编写源程序1。

       （2）采用一维数组用三重循环编写的源程序1。

#include <stdio.h>
#include <string.h>
int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    int n,limw;
    scanf("%d%d",&n,&limw);
    int i,j,k;
    int f[40005];
    memset(f,0,sizeof(f));
    for (i=1;i<=n;i++)
    {
        int v,w,m;
        scanf("%d%d%d",&v,&w,&m);
        for (j=limw;j>=0;j--)
           for (k=0; k<=m &&  k*w<=j; k++)
              f[j]=max(f[j],f[j-k*w]+k*v);
    }
    printf("%d\n",f[limw]);
    return 0;
}

         将上面的源程序提交给洛谷题库P1776 宝物筛选（https://www.luogu.com.cn/problem/P1776），测评结果为“Unaccepted”，其中测试点#4~测试点#10，均显示“TLE”。

        （3）编程思路2。

        采用一维数组用三重循环编写的源程序1显示超时了，为了进行时间优化，采用二进制拆分优化法将多重背包转换为0/1背包进行处理，编写下面的源程序2。

        （4）采用二进制拆分优化法编写的源程序2。

#include <stdio.h>
#include <string.h>
int main()
{
    int n,limw;
    scanf("%d%d",&n,&limw);
    int v[100005],w[100005];
    int i,j;
    int cnt=0;
    for (i=1;i<=n;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        for (j=1;j<=c;j<<=1)
        {
            v[++cnt]=j*a;
            w[cnt]=j*b;
            c-=j;
        }
        if (c)
        {
            v[++cnt]=a*c;
            w[cnt]=b*c;
        }
    }
    int f[40005];
    memset(f,0,sizeof(f));
    for (i=1;i<=cnt;i++)        //  转换为cnt种宝物
        for (j=limw;j>=w[i];j--)
            if (f[j]<f[j-w[i]]+v[i]) f[j]=f[j-w[i]]+v[i];
    printf("%d\n",f[limw]);
    return 0;
}

        将上面的源程序提交给洛谷题库P1776 宝物筛选（https://www.luogu.com.cn/problem/P1776），测评结果为“Accepted”。

 【例8】科技庄园

问题描述

Life种了一块田，里面种了有一些桃树。

Life对PFT说：“我给你一定的时间去摘桃，你必须在规定的时间之内回到我面前，否则你摘的桃都要归我吃！”

PFT思考了一会，最终答应了！

由于PFT的数学不好！它并不知道怎样才能在规定的时间获得最大的价值，

由于PFT不是机器人，所以他的体力并不是无限的，他不想摘很多的桃以至体力为0，而白白把桃给Life。同时PFT每次只能摘一棵桃树，每棵桃树都可以摘K次（对于同一棵桃每次摘的桃数相同）。每次摘完后都要返回出发点（PFT一次拿不了很多）即Life的所在地（0，0），设试验田左上角的桃树坐标是（1，1）。

PFT每秒只能移动一个单位，每移动一个单位耗费体力1（摘取不花费时间和体力,但只限上下左右移动）。

输入

第一行：四个数为N，M，TI，A（10≤N，M，TI，A≤100）分别表示试验田的长和宽，Life给PFT的时间，和PFT的体力。

下面一个N行M列的矩阵桃田。表示每次每棵桃树上能摘的桃数。

接下来N行M列的矩阵，表示每棵桃最多可以采摘的次数K。

输出

一个数：PFT可以获得的最大的桃个数。

输入样例

4 4 13 20

10 0  0  0

0  0  10 0

0  0  10 0

0  0  0  0

1 0 0 0

0 0 2 0

0 0 4 0

0 0 0 0

输出样例

10

         （1）编程思路。

        定义数组int dist[10005],num1[10005],num2[10005]; ，分别用于保存每颗桃树到(0,0)的距离、树上的桃子数、可采摘的次数。

        在输入后进行预处理，每块桃树田中把能摘到桃子的（桃子数量>0）并且可采摘次数>0桃树相关信息分别保存到dist、num1和num2这三个数组中。

        这样，数组中的每颗桃树可以看成一件物品，问题转变为给定体力V、桃树数量N（能摘到桃子的）、每颗桃树最多被采摘K次，在这种情况下最多能摘多少桃子。就是一个典型的多重背包问题了。

        背包容量为V，V受两个条件约束，Life给PFT的时间TI和PFT的体力A。Life给PFT的时间可以转换为体力，因为PFT每秒只能移动一个单位，每移动一个单位耗费体力1，因此给定时间TI就是可供PFT消耗的体力，另外PFT的体力是他实际拥有的体力，FPT最后回去时，体力不能为0，因此至少得留一格体力，这样可确定背包容量V取TI和A-1中的较小值。

        （2）源程序。

#include <stdio.h>
long long max(long long a,long long b)
{
    return a>b?a:b;
}
int main()
{
    int n,m,x,y,v;
    scanf("%d%d%d%d",&n,&m,&x,&y);
    v=x<(y-1)?x:y-1;
    int i,j,k;
    int map[105][105];
    long long f[105]={0};
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            scanf("%d",&map[i][j]);
    int dist[10005],num1[10005],num2[10005]; // 分别表示桃树的距离、桃子数、可采摘的次数
    int cnt=0;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
        {
            int a;
            scanf("%d",&a);
            if (a>0 && map[i][j]>0)
            {
                dist[cnt]=2*(i+j);
                num1[cnt]=map[i][j];
                num2[cnt]=a;
                cnt++;
            }
        }
    for (i=0;i<cnt;i++)
        for (j=v;j>=0;j--)
            for (k=1;k<=num2[i] && k*dist[i]<=j;k++)
                f[j]=max(f[j],f[j-k*dist[i]]+k*num1[i]);
    printf("%lld\n",f[v]);
    return 0;
}

        将上面的源程序提交给洛谷题库P2760 科技庄园（https://www.luogu.com.cn/problem/P2760），测评结果为“Accepted”。

 【例9】硬币

问题描述

有面值分别为A1、A2、…、An的n种硬币，每种硬币各有C1、C2、…、Cn枚。用这些硬币可以组合成多少种不同的不超过m的钱数。

输入                

输入包含几个测试用例。每个测试用例的第一行包含两个整数n（1<=n<=100），m（m<=100000）。第二行包含2n个整数，表示A1，A2，…，An，C1，C2，…，Cn（1<=Ai<=100000，1<=Ci<=1000）。最后一个测试用例后跟两个零。

输出

对于每个测试用例，在一行上输出答案。

输入样例

3 10

1 2 4 2 1 1

2 5

1 4 2 1

0 0

输出样例

8

4

        （1）编程思路1。

        n种硬币，设第i种硬币的面值为Ai，数量为Ci，将这些硬币装入容量为m的背包中，求这些硬币能够组成从1到m中的哪些数字。

        多重背包问题，可采用二进制拆分优化的方法编写如下的源程序1.

​        （2）源程序1。

#include <stdio.h>
#include <string.h>
int main()
{
    int a[101], c[101],w[101];
    int f[100005];
    int n, m;
    while (scanf("%d%d",&n,&m) && (n||m))
    {
        int i,j;
        for (i=1; i<=n; i++)
           scanf("%d",&a[i]);
        for (i=1; i<=n; i++)
           scanf("%d",&c[i]);
       memset(f,0,sizeof f);
       f[0] = 1;
       int ans = 0;
       for (i=1; i<=n; i++)
       {
           int k,cnt=0;
           for (j=1; j<=c[i]; j*=2)  // 多重背包转成0/1背包
           {
              w[++cnt]=j*a[i];
              c[i]-=j;
           }
           if (c[i]>0)
           {
              w[++cnt]=c[i]*a[i];
           }
           for (j=1; j<=cnt; j++)
              for(k=m; k>=w[j]; k--)
                 if (!f[k] && f[k -w[j]])
                 {
                     f[k] = 1;
                     ans++;
                 }
       }
       printf("%d\n",ans);
   }
   return 0;
}

         将上面的源程序1提交给北大OJ题库POJ 1742 Coins（http://poj.org/problem?id=1742），测评结果为“Time Limit Exceeded”，超时。

        （3）编程思路2。

        可以这样来考虑问题。

        对于第i种硬币，如果A i ∗ C i≥m，相当于Ai取的个数没有限制，即可以把第i种硬币的数量视为无穷，作为一个完全背包来求解；否则，就作为一个多重背包来求解。

        （4）源程序2。

#include <stdio.h>
#include <string.h>
int main()
{
    int a[101], c[101],w[101];
    int f[100005];
    int n, m;
    while (scanf("%d%d",&n,&m) && (n||m))
    {
        int i,j;
        for (i=1; i<=n; i++)
           scanf("%d",&a[i]);
        for (i=1; i<=n; i++)
           scanf("%d",&c[i]);
       memset(f,0,sizeof f);
       f[0] = 1;
       int ans = 0;
       for (i=1; i<=n; i++)
       {
           if (a[i] * c[i]>= m)
           {
               for (j=a[i]; j<=m; j++)          // 完全背包
                   if (!f[j] && f[j - a[i]])
                   {
                       f[j] = 1;
                       ans++;
                   }
           }
           else
           {
               int k,cnt=0;
               for (j=1; j<=c[i]; j*=2)      // 多重背包转成0/1背包
               {
                  w[++cnt]=j*a[i];
                  c[i]-=j;
               }
               if (c[i]>0)
               {
                  w[++cnt]=c[i]*a[i];
               }
               for (j=1; j<=cnt; j++)
                  for(k=m; k>=w[j]; k--)
                     if (!f[k] && f[k -w[j]])
                     {
                         f[k] = 1;
                         ans++;
                     }
           }
       }
       printf("%d\n",ans);
   }
   return 0;
}

        将上面的源程序2提交给北大OJ题库POJ 1742 Coins（http://poj.org/problem?id=1742），测评结果为“Accepted”。

        （5）编程思路3。

        也可以这样考虑问题。

        定义数组int f[100010]，其中f[i]表示容量为i的背包是否可以装满，即钱数i是否可以构成。f[i]=1表示i可以构成。初始化时，将数组f全部设为0，f[ 0 ]设为1。

        利用双重循环，外循环i从0到n-1遍历每种硬币A[ i ]，内循环 j 从A[i]开始往后遍历到背包容量m，只要f[ j-A[i] ]==1（即表示钱数j-A[i]能够构成），且f[j]==0（表示钱数j 尚未被构成），则钱数 j 是有可能构成的。

        为什么说有可能呢？是因为能否构成钱数 j，还得看A[i]的数量是否达到上限C[i]。

        为了记录硬币A[i]的使用数量，定义一个专门记录个数的数组sum[M]，在第一层循环内将数组sum[ ]初始化为0，一旦满足f[j -A[i] ] && ! f[ j ] && num[ j - A[ i ] ]<C[i] ，则说明钱数j是可以构成的，则将f[ j ]的值置为1，再将sum[ j ]=num[ j - A[i ] ]+1 表示构成钱数j所对应的面值为A[ i ]的硬币的使用数在钱数为 j-A[ i ]的基础上加1。有了这个sum数组，可以保证硬币A[i]的使用次数不会超过C[i]。

        （6）源程序3。

#include <stdio.h>
#include <string.h>
int f[100010], sum[100010];
int main()
{
    int n,m,i,j,cnt;
    int a[101],c[101];
    while (scanf("%d%d",&n,&m) && n!=0 && m!=0)
    {
       for (i=0;i<n;i++)
           scanf("%d",&a[i]);
       for (i=0;i<n;i++)
          scanf("%d",&c[i]);
       memset(f, 0, sizeof(f));
       f[0] = 1;
       cnt = 0;
       for (i=0; i<n; i++)
       {
            memset(sum, 0, sizeof(sum));
            for (j=a[i]; j<= m; j++)
            {
                if (!f[j] && f[j - a[i]] && sum[j - a[i]] < c[i])
                {
                    f[j] = 1;
                    sum[j] = sum[j-a[i]] + 1;
                    cnt++;
                }
            }
        }
        printf("%d\n",cnt);
    }
    return 0;
}

        将上面的源程序3提交给北大OJ题库POJ 1742 Coins（http://poj.org/problem?id=1742），测评结果为“Accepted”。

 【例10】咖啡自动售货机

问题描述

某咖啡自动售货机只接收面值为1美分、5美分、10美分和25美分的硬币。给定你手里拥有的这4种硬币中每种硬币的数量以及咖啡价格。请给出支付咖啡时必须使用的硬币，要求你使用尽可能多的硬币个数，并且不能找零。

输入

输入包括多组测试用例，每个测试用例用一行输入。

每行输入包含五个整数，每个数用一个空格分隔，描述一种需要解决的情况。第1个整数为P（1<=P<=10000），是以美分为单位的咖啡价格。接下来的四个整数，C1，C2，C3，C4（0<=Ci<=10000），是1美分、5美分、10美分和25美分的硬币个数。输入的最后一行包含五个零，作为测试用例的结束。

输出

对于每种情况，都应该输出一行，其中包含字符串“Throw in T1 cents、T2 nickels、T3 dimes和T4 quarters”，其中T1、T2、T3、T4是在使用尽可能多的硬币的同时，应该使用适当价值的硬币来支付咖啡。如没有足够的零钱来支付咖啡的价格，程序应该输出“Charlie cannot buy coffee.”。

输入样例

12 5 3 1 2

16 0 0 0 1

0 0 0 0 0

输出样例

Throw in 2 cents, 2 nickels, 0 dimes, and 0 quarters.

Charlie cannot buy coffee.

        （1）编程思路。

        4种硬币，面值分别为V[1]、V[2]、V[3]、V[4]，每种硬币的个数分别为C[1]、C[2]、C[3]、C[4]用这4种硬币来组成咖啡的支付价格P。典型的多重背包问题。

        本题在使用多重背包求解时，有两个关键点。

        1）在一般的背包问题里，有容量、价值，所要求的不是最大价值就是最小价值，而定义的f[i][j]表示装有i件物品，容量为j的最大值为f[i][j]，简化为一维的f[j]表示的是在容量为j的时候最大价值为f[j]。在状态转移时，f[j]可以从f[j-v[i]]那边得到值，但它并不需要去判断在f[j-v[i]]前面是否有数可以组成f[j-v[i]]，因此f[j-v[i]]为不为0，不影响最终结果。本题中，f[j]表示构成支付价格j时需要使用的最多硬币数。在状态转移的时候要保证f[j-v[i]]>0（初始时，f[0]=1，其余元素全为0），这是因为题意是要求组成P分钱需要的最多硬币数量，这样要可以组成f[j]，f[j-v[i]]必须要可以组成，否则就会出错。同时，还要保证f[j-v[i]]+1>f[j]（用了面值为V[i]的硬币后，使用的硬币数得多一些才行）且硬币的使用个数不超过c[i]（可参考上面例9的编程思路3）。

        2）要求出各种硬币使用多少个，需要记录路径，为此定义数组path[10010]，在状态由f[j-v[i]]到f[j]转移时，记录path[j]=j-v[i]，这样，j-path[j]=j-(j-v[i])=v[i]，而v[i]正好是硬币的面值，可以对相应面值的硬币使用个数进行计数。

        （2）源程序。

#include <stdio.h>
#include <string.h>
int main()
{
    int f[10010],ans[10010],num[10010],path[10010];
    int c[5]={0,1,5,10,25};
    int t[5],p;
    while (scanf("%d%d%d%d%d",&p,&t[1],&t[2],&t[3],&t[4])&&(p||t[1]||t[2]||t[3]||t[4]))
    {
        memset(f,0,sizeof(f));
        memset(ans,0,sizeof(ans));
        memset(path,0,sizeof(path));
        f[0]=1;
        int i,j;
        for (i=1;i<=4;i++)
        {
            memset(num,0,sizeof(num));
            for (j=c[i];j<=p;j++)
                if (f[j-c[i]] && f[j-c[i]]+1>f[j] && num[j-c[i]]<t[i])
                {
                    f[j]=f[j-c[i]]+1;
                    num[j]=num[j-c[i]]+1;
                    path[j]=j-c[i];
                }
        }
        if (f[p]>0)
        {
            i=p;
            while(i!=0)
            {
                ans[i-path[i]]++;
                i=path[i];
            }
            printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n",ans[1],ans[5],ans[10],ans[25]);
        }
        else
            printf("Charlie cannot buy coffee.\n");
    }
    return 0;
}

         将上面的源程序提交给北大OJ题库POJ 1787 Charlie's Change（http://poj.org/problem?id=1787），可以Accepted。 

练习题

1．P6771 [USACO05MAR]Space Elevator 太空电梯（https://www.luogu.com.cn/problem/P6771）

#include <stdio.h>
#include <string.h>
struct Node
{
    int h,a,c;
};
int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    int k;
    scanf("%d",&k);
    struct Node block[405];
    int f[40500]={0};
    int i,j;
    for (i=1;i<=k;i++)
    {
        scanf("%d%d%d",&block[i].h,&block[i].a,&block[i].c);
    }
    for (i=1;i<k;i++)
        for (j=1;j<=k-i;j++)
            if (block[j].a>block[j+1].a)
            {
                struct Node temp;
                temp=block[j]; block[j]=block[j+1]; block[j+1]=temp;
            }
    for (i=1;i<=k;i++)
    {
        int n;
        for (n=1;n<=block[i].c;n++)     //多重背包
        {
            for (j=block[i].a;j>=block[i].h;j--)
            {
                f[j]=max(f[j],f[j-block[i].h]+block[i].h);
            }
        }
    }
    int ans=0;
    for (i=1;i<=block[k].a;i++)
        ans=max(ans,f[i]);
    printf("%d\n",ans);
    return 0;
}

参考源程序1

#include <stdio.h>
#include <string.h>
struct Node
{
    int h,a,c;
};
int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    int k;
    scanf("%d",&k);
    struct Node block[405];
    int f[40500]={0};
    int i,j;
    for (i=1;i<=k;i++)
    {
        scanf("%d%d%d",&block[i].h,&block[i].a,&block[i].c);
    }
    for (i=1;i<k;i++)
        for (j=1;j<=k-i;j++)
            if (block[j].a>block[j+1].a)
            {
                struct Node temp;
                temp=block[j]; block[j]=block[j+1]; block[j+1]=temp;
            }
    for (i=1;i<=k;i++)
    {
        if (block[i].a>block[i].c*block[i].h)
        {
            int n;
            for (n=1;n<block[i].c;n*=2)
            {
                for (j=block[i].a;j>=block[i].h*n;j--)
                {
                    f[j]=max(f[j],f[j-block[i].h*n]+block[i].h*n);
                }
                block[i].c-=n;
            }
            if (block[i].c>0)
            {
                for (j=block[i].a;j>=block[i].h*block[i].c;j--)
                f[j]=max(f[j],f[j-block[i].h*block[i].c]+block[i].h*block[i].c);
            }
        }
        else
        {
            for (j=block[i].h;j<=block[i].a;j++)
            {
                f[j]=max(f[j],f[j-block[i].h]+block[i].h);
            }
        }
    }
    int ans=0;
    for (i=1;i<=block[k].a;i++)
        ans=max(ans,f[i]);
    printf("%d\n",ans);
    return 0;
}