首页 > 代码库 > hdu2191（多重背包）

hdu2191（多重背包）

2024-08-04 16:42:15   222人阅读

 

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2191

 

分析：

========================================

多重背包问题定义 & 基本实现

问题：有个容量为V大小的背包，有很多不同重量weight[i](i=1..n)不同价值value[i](i=1..n)的货物，第i种物品最多有n[i]件可用，计算一下最多能放多少价值的货物。

对于多重背包的基本实现，与完全背包是基本一样的，不同就在于物品的个数上界不再是v/c[i]而是n[i]与v/c[i]中较小的那个。状态转移方程如下

1
f(i,v) = max{ f(i-1,v-k*c[i]) + k*w[i] | 0<=k<=n[i] }

代码与完全背包的区别仅在内部循环上由

1
for(k = 1; k <= j/weight[i]; ++k)

变为

1
for(k = 1; k <=n[i] && k<=j/weight[i]; ++k)

当然，输入上的区别就不说了。

 

========================================

多重背包二进制拆分实现

跟完全背包一样的道理，利用二进制的思想将n[i]件物品i拆分成若干件物品，目的是在0-n[i]中的任何数字都能用这若干件物品代换，另外，超过n[i]件的策略是不允许的。

方法是将物品i分成若干件，其中每一件物品都有一个系数，这件物品的费用和价值都是原来的费用和价值乘以这个系数，使得这些系数分别为1,2,4,…,2^(k-1),n[i]-2^k+1，且k满足n[i]-2^k+1>0的最大整数。例如，n[i]=13，就将该物品拆成系数为1、2、4、6的四件物品。分成的这几件物品的系数和为n[i]，表明不可能取多于n[i]件的第i种物品。另外这种方法也能保证对于0..n[i]间的每一个整数，均可以用若干个系数的和表示。

 

#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long long#define inf 1<<30#define mod 1000000007using namespace std;int p[1010],w[1010];int dp[1010],v,n;int main(){    int t;    scanf("%d",&t);    while(t--)    {        scanf("%d%d",&v,&n);        int sum=1;        for(int i=1;i<=n;i++)        {            int cost,price,num;            scanf("%d%d%d",&cost,&price,&num);            for(int j=1;j<=num;j*=2)            {                w[sum]=j*cost;                p[sum++]=j*price;                num-=j;            }            if(num>0)            {                w[sum]=num*cost;                p[sum++]=num*price;            }        }        memset(dp,0,sizeof(dp));        for(int i=1;i<sum;i++)            for(int j=v;j>=w[i];j--)            dp[j]=max(dp[j],dp[j-w[i]]+p[i]);        printf("%d\n",dp[v]);    }}
View Code

 

hdu2191（多重背包）


联系
我们