混合背包C的特点和适用场景有哪些？
- 内容介绍
- 文章标签
- 相关推荐
本文共计606个文字，预计阅读时间需要3分钟。
题目描述：一位旅行者有一个最大容量为V的背包，现有n件物品，它们的重量分别为W1，W2，...，Wn，价值分别为C1，C2，...，Cn。物品只能取一次（即一次只能取一个物品放入背包），求背包能装载物品的最大价值。
题目描述】 一个旅行者有一个最多能装V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn ，它们的价值分别为C1,C2,...,Cn 。有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
第一行：二个整数，M(背包容量，M<=200)，N(物品数量，N<=30)；
第2..N+1行：每行三个整数Wi,Ci,Pi ，前两个整数分别表示每个物品的重量，价值，第三个整数若为0，则说明此物品可以购买无数件，若为其他数字，则为此物品可购买的最多件数(Pi )。
仅一行，一个数，表示最大总价值。
10 3 2 1 0 3 3 1 4 5 4 11 选第一件物品1件和第三件物品2件。
#include <iostream>
#include<cmath>
#include<vector>
using namespace std;
const int N=35;
int m,n; // 背包容量、物品数
int dp[205]; // 在容量不超过i时所能获得的最大的价值
int w[N],c[N],p[N]; // 重量、价值、数量
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>m>>n;
for(int i=1;i<=n;i++)
{
cin>>w[i]>>c[i]>>p[i];
}
for(int i=1;i<=n;i++) // 对每一种物品
{
if(p[i]==0) // 如果为0是完全背包
{
for(int j=w[i];j<=m;j++)// 完全背包当前容量从小到大
{
dp[j] = max(dp[j],dp[j-w[i]]+c[i]);
}
}else // 大于0是 01背包或多重背包
{
for(int j=m;j>=w[i];j--)// 多重背包和01背包当前容量从大到小
{
for(int k=0;k<=p[i];k++)
{
if(j<k*w[i])break; // 当容量不够时要及时退出
dp[j]= max(dp[j],dp[j-k*w[i]]+k*c[i]);
}
}
}
}
cout<<dp[m];
return 0;
}
本文共计606个文字，预计阅读时间需要3分钟。
题目描述：一位旅行者有一个最大容量为V的背包，现有n件物品，它们的重量分别为W1，W2，...，Wn，价值分别为C1，C2，...，Cn。物品只能取一次（即一次只能取一个物品放入背包），求背包能装载物品的最大价值。
题目描述】 一个旅行者有一个最多能装V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn ，它们的价值分别为C1,C2,...,Cn 。有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
第一行：二个整数，M(背包容量，M<=200)，N(物品数量，N<=30)；
第2..N+1行：每行三个整数Wi,Ci,Pi ，前两个整数分别表示每个物品的重量，价值，第三个整数若为0，则说明此物品可以购买无数件，若为其他数字，则为此物品可购买的最多件数(Pi )。
仅一行，一个数，表示最大总价值。
10 3 2 1 0 3 3 1 4 5 4 11 选第一件物品1件和第三件物品2件。
#include <iostream>
#include<cmath>
#include<vector>
using namespace std;
const int N=35;
int m,n; // 背包容量、物品数
int dp[205]; // 在容量不超过i时所能获得的最大的价值
int w[N],c[N],p[N]; // 重量、价值、数量
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>m>>n;
for(int i=1;i<=n;i++)
{
cin>>w[i]>>c[i]>>p[i];
}
for(int i=1;i<=n;i++) // 对每一种物品
{
if(p[i]==0) // 如果为0是完全背包
{
for(int j=w[i];j<=m;j++)// 完全背包当前容量从小到大
{
dp[j] = max(dp[j],dp[j-w[i]]+c[i]);
}
}else // 大于0是 01背包或多重背包
{
for(int j=m;j>=w[i];j--)// 多重背包和01背包当前容量从大到小
{
for(int k=0;k<=p[i];k++)
{
if(j<k*w[i])break; // 当容量不够时要及时退出
dp[j]= max(dp[j],dp[j-k*w[i]]+k*c[i]);
}
}
}
}
cout<<dp[m];
return 0;
}