首页 > 代码库 > 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 多重背包
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。