背包问题
参考
1、https://blog.csdn.net/qq_54847231/article/details/123850995
2、https://blog.csdn.net/qq_41765114/article/details/88412863
1、01背包问题
描述
一共n件物品，背包容量为v，求将哪些物品装入背包，求解如何装，使得背包内总价值最大
0< N,V ≤ 1000
示例
//输入
4 5
1 2
2 4
3 4
4 5
//输出
8
二维
void bag2() {
int n;
cin >> n;
int v;
cin >> v;
int dp[n+1][v+1];
int vv[n+1],ww[n+1];
for(int i = 1; i <= n ; i++) {
cin >> vv[i] >> ww[i];
dp[i][0] = 0;
}
for(int i = 0 ; i <= v ; i++) {
dp[0][i] = 0;
}
for(int i = 1; i <= n ; i++) {
//j为假设背包上限
for(int j = 1; j <= v ; j++) {
//当背包容量为j，判断是否能装下当前物品
if(j < vv[i]) {
//放不下i件物品，则不再放
dp[i][j] = dp[i-1][j];
} else {
//判断替换或增加一件物品与不放物品时的价值
dp[i][j] = max(dp[i-1][j],dp[i-1][j - vv[i]] + ww[i]);
}
}
}
cout << dp[n][v] << endl;
}
一维
void bag1() {
//n件物品，容量为m
int n,m;
cin >> n >> m;
int dp[m+1];
for(int i = 0 ; i <= m ; i++)
dp[i] = 0;
int v,w;
for(int i = 1 ; i <= n ; i++) {
cin >> v >> w;
//从大到小遍历，即所有东西只装一件
for(int j = m ; j >= 0; j--) {
if(j < v)
break;
//如果可以装下，判断换个物品的价值
dp[j] = max(dp[j],dp[j - v] + w);
}
}
cout << dp[m];
}
2、完全背包问题
描述
一共n件物品，背包容量为v，求将哪些物品装入背包，求解如何装，使得背包内总价值最大
每件物品都无限件可用
0< N,V ≤ 1000
示例
//输入
4 5
1 2
2 4
3 4
4 5
//输出
10
二维
void bag2() {
//物品种数和背包容积
int n,m;
cin >> n >> m;
int v[n+1],w[n+1];
int dp[n+1][m+1];
//体积和价值
for(int i = 1; i <= n; i++) {
cin >> v[i] >> w[i];
}
//初始化状态数组
for(int i = 0; i <= n; i++)
for(int j = 0; j <= m; j++)
dp[i][j] = 0;
for(int i = 1; i <= n; i++) {
for(int j = 0; j <= m; j++) {
dp[i][j] = dp[i-1][j];
if(j >= v[i])
dp[i][j] = max(dp[i][j],dp[i][j - v[i]] + w[i]);
}
}
cout << dp[n][m] << endl;
}
一维
void bag1() {
int n,m;
cin >> n >> m;
int dp[m+1];
for(int i = 0; i <= m; i++)
dp[i] = 0;
int v,w;
for(int i = 1; i <= n; i++) {
cin >> v >> w;
for(int j = v ; j <= m; j++) {
dp[j] = max(dp[j],dp[j - v] + w);
}
}
cout << dp[m] << endl;
}
3、多重背包问题
描述
一共n件物品，背包容量为v，求将哪些物品装入背包，求解如何装，使得背包内总价值最大
每件物品都无限件可用
0< N,V ≤ 100
示例
//输入
4 5
1 2 3
2 4 1
3 4 3
4 5 2
//输出
10
二维
void bag2(){
int n,m;
cin >> n >> m;
int v,w,s;
list<int> vv,ww;
for(int i = 1; i <= n; i++) {
//输入大小、价值、个数
cin >> v >> w >> s;
//以1、2、4...的倍数放入物品
for(int j = 1; j <= s; ) {
vv.push_back(j*v);
ww.push_back(j*w);
s -= j;
j *= 2;
}
//最后多余的物品为一组
if(s > 0) {
vv.push_back(s*v);
ww.push_back(s*w);
}
}
list<int>::iterator itv=vv.begin();
list<int>::iterator itw=ww.begin();
int dp[vv.size()+1][m+1];
for(int i = 0; i <= vv.size(); i++)
dp[i][0] = 0;
for(int i = 0; i <= m; i++)
dp[0][i] = 0;
//01背包
for(int i = 1; i <= vv.size(); i++) {
for(int j = 1; j <= m; j++) {
dp[i][j] = dp[i-1][j];
if(j >= *itv)
dp[i][j] = max(dp[i][j],dp[i-1][j-*itv] + *itw);
}
itv++;
itw++;
}
}
一维
void bag1() {
int n,m;
cin >> n >> m;
int v,w,s;
list<int> vv,ww;
for(int i = 1; i <= n; i++) {
//输入大小、价值、个数
cin >> v >> w >> s;
//以1、2、4...的倍数放入物品
for(int j = 1; j <= s; ) {
vv.push_back(j*v);
ww.push_back(j*w);
s -= j;
j *= 2;
}
//最后多余的物品为一组
if(s > 0) {
vv.push_back(s*v);
ww.push_back(s*w);
}
}
list<int>::iterator itv=vv.begin();
list<int>::iterator itw=ww.begin();
int dp[m+1];
for(int i = 0; i <= m; i++)
dp[i] = 0;
//01背包
for(int i = 1; i <= vv.size(); i++) {
for(int j = m; j >= 0; j--) {
if(j >= *itv)
dp[j] = max(dp[j],dp[j-*itv] + *itw);
}
itv++;
itw++;
}
}
4、分组背包问题
描述
一共n组物品，背包容量为v，求将哪些物品装入背包，求解如何装，使得背包内总价值最大
每组有若干件物品，同组内最多选一个
每件物品体积为ij，i是组号，j是组内编号
0< N,V ≤ 100
示例
//输入
3 5 //n组，容量v
2 //i组有s件物品
1 2
2 4
1
3 4
1
4 5
//输出
8
二维
void bag2() {
int n,m;
cin >> n >> m;
int v[n+1][201],w[n+1][201];
int s[n+1];
for(int i = 1; i <= n; i++) {
cin >> s[i];
v[i][0] = 0;
w[i][0] = 0;
for(int j = 1;j <= s[i]; j++) {
cin >> v[i][j] >> w[i][j];
}
}
int dp[n+1][m+1];
for(int i = 0; i <= m; i++)
dp[0][i] =0;
for(int i = 0; i <= n; i++)
dp[i][0] =0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
dp[i][j] = dp[i-1][j];
//加个组循环（类似于完全背包问题）
for(int k = 0;k <= s[i]; k++) {
if(j >= v[i][k])
dp[i][j] = max(dp[i][j],dp[i-1][j-v[i][k]] + w[i][k]);
}
}
}
}
一维
void bag1() {
int n,m;
cin >> n >> m;
int v[n+1][201],w[n+1][201];
int s[n+1];
for(int i = 1; i <= n; i++) {
cin >> s[i];
v[i][0] = 0;
w[i][0] = 0;
for(int j = 1;j <= s[i]; j++) {
cin >> v[i][j] >> w[i][j];
}
}
int dp[m+1];
for(int i = 0; i <= m; i++)
dp[i] =0;
for(int i = 1; i <= n; i++) {
for(int j = m; j >= 0; j--) {
for(int k = 0;k <= s[i]; k++) {
if(j >= v[i][k])
dp[j] = max(dp[j],dp[j-v[i][k]] + w[i][k]);
}
}
}
}
5、最优装配
给出 n 个物体，重量分别为 wi，使总重量不超过容量 C 的情况下选择尽量多的物体。
只需要使用贪心算法
示例
//输入
4 10
5
2
3
1
//输出
3
代码
void bag() {
int n,m;
cin >> n >> m;
int w[n];
for(int i = 0; i < n; i++) {
cin >> w[i];
}
//排序，从小到大
sort(w,w+n);
int sum = 0;
for(int i = 0; (sum + w[i]) <= m; i++) {
sum += w[i];
cout << w[i] <<" ";
}
cout << endl;
}
6、部分背包问题
有 n 个物体，重量分别为 wi，价值为 vi，在总重量不超过容量 C 的情况下让总价值最高，
每个物体可以只取走一部分，若取走部分物体则价值也会等比例减少。
计算每件物品的性价比，先取性价比更高的物品
示例
//输入
4 9
1 2 //2
2 4 //2
4 4 //1
4 5 //1.25
//输出
1 2 1
2 4 3
4 5 7
0.5 2 2
struct Stuff{
int weight;
int value;
float rate;
bool operator < (Stuff other) const {
return rate > other.rate;
}
};
void bag() {
int n,m;
cin >> n >> m;
Stuff* stuff = new Stuff[n];
for(int i = 0; i < n; i++) {
cin >> stuff[i].weight >> stuff[i].value;
stuff[i].rate = stuff[i].value * 1.0/stuff[i].weight;
}
sort(stuff,stuff+n);
int sum = 0;
for(int i = 0; i < n; i++) {
if((stuff[i].weight + sum) <= m) {
sum += stuff[i].weight;
cout << stuff[i].weight << " " << stuff[i].value << " " << sum << endl;
} else {
float num = (m - sum) * 1.0 /stuff[i].weight * 1.0;
cout << num << " " <<stuff[i].weight * num << " " << stuff[i].value * num << endl;
break;
}
}
}
|