51nod 多重背包问题（动态规划）

多重背包问题

一个背包，承量有限为W，有n种物体，第i种物体，价值Vi，占用重量为 Wi，且有Ci件，选择物品若干放入背包，使得总重量不超过背包的承重。总价值最大？

输入

第1行，2个整数，N和W中间用空格隔开。N为物品的种类，W为背包的容量。(1 <= N <= 100，1 <= W <= 50000)
第2 - N + 1行，每行3个整数，Wi，Pi和Ci分别是物品体积、价值和数量。(1 <= Wi, Pi <= 10000， 1 <= Ci <= 200)

输出

输出可以容纳的最大价值。

输入示例

输出示例

请选取你熟悉的语言，并在下面的代码框中完成你的程序，注意数据范围，最终结果会造成Int32溢出，这样会输出错误的答案。

不同语言如何处理输入输出，请查看下面的语言说明。

【分析】我们把第i种物品看成单个的，一个一个的，我们想想二进制，任何一个数都可以由二的幂表示。

我们试试看，比如Ci = 14，我们可以把它化成如下4个物品：

重量是Wi，体积是Vi
重量是2 * Wi , 体积是2 * Vi
重量是4 * Wi , 体积是4 * Vi
重量是7 * Wi , 体积是7 * Vi

注意最后我们最后我们不能取，重量是8 * Wi , 体积是8 * Vi 因为那样总的个数是1 ＋ 2 ＋ 4 ＋ 8 ＝ 15个了，我们不能多取对吧？

我们用这4个物品代替原来的14个物品，大家可以试试原来物品无论取多少个，重量和体积都可以靠我们这几个物品凑出来，这说明我们这种分配方式和原来是等价的。

我们转化为一般方法，对于Ci ,我们的拆分方法是：

1，2，4，8…… 同时Ci减去这些值，如果Ci不够减了，则把最后剩余的算上，同时我们体积也对应乘以这些系数。这样Ci个同一种物品，被我们变成了logCi个物品了。于是按照0-1背包的做法，时间复杂变为O(W * sigma(logCi))了，降了很多。

（关于此题还有复杂度更低的方法，留作大家思考）

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std ;
ll n,m,a[50005],dp[50005];
ll b[505],w[20005],v[20005];
int main()
{
    int W,V,C,cnt=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>W>>V>>C;
        for(int j=1;;j*=2)
        {
            if(C>=j){w[cnt]=j*W;v[cnt]=j*V;C-=j;cnt++;}
            else {w[cnt]=C*W;v[cnt]=C*V;cnt++;break;}
        }
    }

    for(int i=0;i<cnt;i++)
    {
        for(int j=m;j>=w[i];j--)
        {
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
    cout<<dp[m]<<endl;
    return 0 ;
}

View Code

51nod 多重背包问题（动态规划）

推荐阅读