题目:携带矿石资源
题目:
56 卡码网 携带矿石资源
多重背包的每种物品的个数不相同但都是有限个,
动态规划
在01背包的基础上,加上一个数量的循环判断
即在01背包的两层for循环内,加上一个物品个数的循环嵌套
代码
#include<iostream>
#include<vector>
using namespace std;
int main(){
int C,N;
cin>>C>>N;//容量 种类
//重量数组
vector<int> weight(N,0);
vector<int> value(N,0);
vector<int> nums(N,0);
for(int i=0;i<weight.size();i++){
cin>>weight[i];
}
for(int i=0;i<value.size();i++){
cin>>value[i];
}
for(int i=0;i<nums.size();i++){
cin>>nums[i];
}
//初始化dp数组
vector<int> dp(C+1,0);
//遍历顺序
//先遍历物品后倒序遍历背包
for(int i=0;i<weight.size();i++){
for(int j=C;j>=weight[i];j--){
for(int k=0;k<=nums[i]&&j>=k*weight[i];k++){
dp[j]=max(dp[j],dp[j-k*weight[i]]+k*value[i]);
}
}
}
cout<<dp[C]<<endl;
return 0;
}
时间复杂度:O(m × n × k),m:物品种类个数,n背包容量,k单类物品数量
空间复杂度:O(n)