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

hdu2191 多重背包

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

多重背包:有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用,每件费用是c[i],价值是w[i]。

              求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

有两种思路,其中一种是转换为01背包,还有一种就是转换为01背包和完全背包。

转换为01背包代码:

//转换为01背包的代码#include<iostream>#include<algorithm>#include<cstring>using namespace std;const int N=105;const int MAXW=4005;int v[N],w[N],num[N];int dp[MAXW];int main(){    int t;    cin>>t;    while(t--)    {        int n,m;        cin>>n>>m;        for(int i=0; i<m; i++)            cin>>w[i]>>v[i]>>num[i];        memset(dp,0,sizeof(dp));        for(int i=0; i<m; i++)            for(int j=1; j<=num[i]; j++)                for(int k=n; k>=w[i]; k--)                    dp[k]=max(dp[k],dp[k-w[i]] +v[i]);        cout<<dp[n]<<endl;    }    return 0;}

 

hdu2191 多重背包