动态规划——多重背包问题

写在前面

由于本人实力尚浅，接触算法没多久，写这篇blog仅仅是想要提升自己对算法的理解，如果各位读者发现什么错误，恳请指正，希望和大家一起进步。(●’◡’●)

如果没看过我前面关于01背包问题（良心正解）和完全背包问题（良心正解）的宝宝可以先去看看，可以让你对动态规划的理解更透彻

DP核心思路

多重背包问题

题目

思路

重要变量说明

f[][[]:用于状态表示；

w[]：记录每个物品的价值；

v][]：记录每个物品的体积；

cnt[]:记录每个物品的数量；

1. 定义二维数组f[][],其中f[i][j]表示在前i个物品，背包容积为j的限制下所能装下的最大价值。这里的f[i][j]就是做法的集合，f[i][j]的值就是最大价值即属性。
2. 从i=1开始枚举，对于第i个物品，都有一定数量的选择：
   • 如果不选第i个物品，那么状态转移方程为f[i][j]=f[i-1][j]
   • 如果选择第i个物品一次，那么状态转移方程为f[i][j]=f[i-1][j-v[i]]+w[i]
   • ......
   • 如果选择第i个物品cnt[i]次（即每个物品的最大数量），那么状态转移方程为f[i][j]=max(f[i-1][j-cnt[i]*v[i]]+cnt[i]*w[i](前提是不超过当前背包的容积）
   • 我们因为要求最大价值，所以对上面两种情况去max即可。

代码（不优化）

二维数组

#include
using namespace std;
const int N=110;
int v[N],w[N],f[N][N],cnt[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i>v[i]>>w[i]>>cnt[i];
    for(int i=1;i
    int n,m;
    cinnm;
    for(int i=1;iw[i]>>cnt[i];
    for(int i=1;i=0;j--)
            for(int k=0;k
    int n,m;
    cinnm;
    int cnt=0;
    for(int i=1;i
        int a,b,c,k=1;
        cina>>b>>c;
        while(k
            v[++cnt]=a;
            w[cnt]=b;
            k++;
        }
    }
    for(int i=1;i>c;
        while(k
            v[++cnt]=k*a;
            w[cnt]=k*b;
            c-=k;
            k*=2;
        }
        if(c)
        {
            v[++cnt]=c*a;
            w[cnt]=c*b;
        }

    int n,m;
    cin>n>>m;
    int cnt=0;
    for(int i=1;i
        int a,b,c,k=1;
        cin>a>>b>>c;
        while(k
            v[++cnt]=k*a;
            w[cnt]=k*b;
            c-=k;
            k*=2;
        }
        if(c)
        {
            v[++cnt]=c*a;
            w[cnt]=c*b;
        }
    }
    for(int i=1;i