动态规划-多重背包（含全部代码）

题目：假设你是一个小偷，有一个可放总重量为m(m<1000)的背包。现有n(n<32)件物品。
      总量分别为W1,W2,...，Wn。物品具有价值，分别为V1,V2,...,Vn。并且，物品是有限个，
      数量分别为N1,N2,...Nn。m、n、Wi,Vi,Ni(1=<i<=n)均为正整数，求能装入的最大总价值。
输入格式：
第一行为两个正整数m和n
接下来n行分别为n行整数，每行三个，分别表示该物品的重量、价值和数量。      
Example:
Input:
8 2
2 100 4
1 200 2
Output：
700
【分析】 增加了数量，需要进行各种数量组合的判断
          状态转移方程：
          dp[k]=max(dp[k],dp[k-W[i]]+V[i])，dp[k]表示前i种物品,在背包能放入重量为k时，
          装入数量为j的第i种物品时的最大价值

代码：

/*
Project: dp_MulBag
Date:    2019/01/12
Author:  Frank Yu
题目：假设你是一个小偷，有一个可放总重量为m(m<1000)的背包。现有n(n<32)件物品。
      总量分别为W1,W2,...，Wn。物品具有价值，分别为V1,V2,...,Vn。并且，物品是有限个，
      数量分别为N1,N2,...Nn。m、n、Wi,Vi,Ni(1=<i<=n)均为正整数，求能装入的最大总价值。 
输入格式：
第一行为两个正整数m和n
接下来n行分别为n行整数，每行三个，分别表示该物品的重量、价值和数量。   
Example:
Input:
8 2
2 100 4
1 200 2
Output： 
700 
【分析】 增加了数量，需要进行各种数量组合的判断 
          状态转移方程：
          dp[k]=max(dp[k],dp[k-W[i]]+V[i])，dp[k]表示前i种物品,在背包能放入重量为k时，
          装入数量为j的第i种物品时的最大价值 
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<set>
#include<list>
#include<vector>
#include<map>
#include<iterator>
#include<algorithm>
#include<iostream>
#define maxm 1000
#define maxn 32
using namespace std;
int W[maxn],V[maxn],N[maxn];
//打印表 
void display(int dp[maxn],int m)
{
    for(int i=0;i<=m;i++)
     {
        printf("%d ",dp[i]);
     }
     printf("\n");
}
//主函数 
int main()
{
    int m, n;
    int dp[maxn];
    dp[0]=0;
    scanf("%d", &m);//背包重量 
    scanf("%d", &n);//物品种类 
    for (int i = 1;i <= n;i++)//下标即第几件物品,W[0]一直为0
    {
        scanf("%d",&W[i]);
        scanf("%d",&V[i]);
        scanf("%d",&N[i]);
    }
     //填表
     for(int i=1;i<=n;i++)           //遍历每件物品 
        for(int j=0;j<N[i];j++)     //尝试各种数量 
          for(int k=m;k>=W[i];k--)   //计算各种重量背包的能放下的各种组合的价值 
          {
           int choose = dp[k-W[i]]+V[i];//选了，价值增加 
            if(choose>dp[k])dp[k]=choose;
          }
     display(dp,m);     
     printf("%d",dp[m]);
    return 0;
}

结果截图：