DP大作战—组合背包

题目描述

组合背包：有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。

DD大牛的伪代码

for i = 1 to N

    if 第i件物品属于01背包

        ZeroOnePack(F,Ci,Wi)

    else if 第i件物品属于完全背包

        CompletePack(F,Ci,Wi)

    else if 第i件物品属于多重背包

        MultiplePack(F,Ci,Wi,Ni)

输入

第一个数为数据组数n 1<=n<=10

接下来n组测试数据，每组测试数据由2部分组成。

第一行为背包容量V，物品种类数N。1<=V<=30000,1<=N<=200

接下来N行每行三个数为物品价值v，物品重量w，物品件数M。M=233表示物品无限。

1<=v,w<=200, 1<=M<=25

输出

对于每组数据，输出一行，背包能容纳的最大物品价值

输入样例

输出样例

13
题目来源：http://biancheng.love/contest/10/problem/F/index
解题思路：
组合背包：0-1背包、完全背包、多重背包。
因此需要结合上述三种背包问题的解决方法来solve组合背包
0-1背包代码：

 void Zeronepack(int w,int v)

 {

     for(int i=V; i>=w; i--)

         if(dp[i]<dp[i-w]+v)

             dp[i]=dp[i-w]+v;

 }

完全背包代码：

 void Compack(int w,int v)

 {

     for(int i=w; i<=V; i++)

         if(dp[i]<dp[i-w]+v)

             dp[i]=dp[i-w]+v;

 }

多重背包代码：

 void Multipack(int w,int v,int num)

 {

     int k;

     if(w*num>=V)

     {

         Compack(w,v);

         return;

     }

     for(k=; k<num; k<<)

     {

         Zeronepack(k*w,k*v);

         num-=k;

     }

     Zeronepack(num*w,num*v);

 }

本题组合背包代码：

 #include <bits/stdc++.h>

 int dp[];

 int V,N;

 void Compack(int w,int v)

 {

     for(int i=w; i<=V; i++)

         if(dp[i]<dp[i-w]+v)

             dp[i]=dp[i-w]+v;

 }

 void Zeronepack(int w,int v)

 {

     for(int i=V; i>=w; i--)

         if(dp[i]<dp[i-w]+v)

             dp[i]=dp[i-w]+v;

 }

 void Multipack(int w,int v,int num)

 {

     int k;

     if(w*num>=V)

     {

         Compack(w,v);

         return;

     }

     for(k=; k<num; k<<)

     {

         Zeronepack(k*w,k*v);

         num-=k;

     }

     Zeronepack(num*w,num*v);

 }

 int main()

 {

     int kase,v,w,m;

     scanf("%d",&kase);

     while(kase--)

     {

         memset(dp,,sizeof(dp));

         scanf("%d%d",&V,&N);

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

         {

             scanf("%d%d%d",&v,&w,&m);

             if(m==)

                 Zeronepack(w,v);

             else if(m==)

                 Compack(w,v);

             else

                 Multipack(w,v,m);

         }

         printf("%d\n",dp[V]);

     }

     return ;

 }

巴特西

DP大作战—组合背包

题目描述

输入

输出

输入样例

输出样例

最新文章

热门文章