首页 > 代码库 > 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个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。