多重背包和完全背包
2026-01-18 18:19:45
发布于：广东
4阅读
0回复
0点赞
//第二版:优化方案时间复杂度:N*C,空间复杂度C
// #include<bits/stdc++.h>
// using namespace std;
// const int N=1e7+10;
// #define ll long long
// int w[N],v[N];//重量和价值
// ll dp[N];//在容量为j的时候最大价值
// void solve(){
// int c,n;//c的容量,n个物品
// cin>>n;
// for(int i=1;i<=n;i++){
// int x;
// cin>>x>>w[i]>>v[i];//存储每个物品的重量和价值
// }
// cin>>c;
// for(int i=1;i<=n;i++){
// for(int j=0;j<=c;j++){ //01背包/完全背包(无限背包)
// if(j-w[i]>=0){//判断是否可以选择当前的物品,选择当前的物品i产生v[i]的价值
// dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
// }
// }
// }
// cout<<dp[c];//选完最后一个物品,并且容量为c的情况即为答案
// }
// int main(){
// int t=1;
// // cin>>t;
// while(t--){
// solve();
// }
// }
//01背包 <--> 01 选择或者不选
//完全背包(无限背包) <--> 对于任何物品可以无限的进行选择
//多重背包 <--> 对于第i个物品最多只能选择num[i]个可以转化为01背包问题 01背包
//k 24 (1 2 4 8 9)
//给定一个数字n,你可以将n进行任意的拆分,使得拆分之后的和依旧为n
//并且拆分之后的数字.可以选择其中一部分组合为1-n里面的所有数字
//最少需要多少个数字,并且输出这些数字
// #include<bits/stdc++.h>
// using namespace std;
// const int N=2e5+10;
// #define ll long long
// void solve(){
// int n;
// cin>>n;
// int inx=1;
// while(n>=inx){
// cout<<inx<<endl;
// n-=inx;
// inx*=2;
// }
// cout<<n<<endl;
// }
// int main(){
// int t=1;
// // cin>>t;
// while(t--){
// solve();
// }
// }
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
#define ll long long
int w[N],v[N];//重量和价值
ll dp[N];//在容量为j的时候最大价值
void solve(){
int c,n;//c的容量,n个物品
cin>>c;
cin>>n;
int num=0;//计数
for(int i=1;i<=n;i++){
int a,b,c;//分别对应重量价值,数量
int inx=1;//个数
while(c>=inx){
w[++num]=inx*a;
v[num]=inx*b;
c-=inx;
inx*=2;
}
if(c){
w[++num]=c*a;
v[num]=c*b;
}
}
for(int i=1;i<=num;i++){
for(int j=c;j>=0;j--){ //01背包/完全背包(无限背包)
if(j-w[i]>=0){//判断是否可以选择当前的物品,选择当前的物品i产生v[i]的价值
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
}
cout<<dp[c];//选完最后一个物品,并且容量为c的情况即为答案
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
这里空空如也
有帮助，赞一个