c++题目_背包问题（可任意分割） 贪心算法

 

题目描述

有一个背包，背包容量是mm。有nn个物品，每个物品都有自己的重量wiw​i​​和价值viv​i​​，物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

输入

第一行输入两个正整数 mm 和 nn (1≤m,n≤10000)(1≤m,n≤10000) 分别代表背包容量和物品的个数
第二行输入 nn 个正整数 表示每个物品的重量 wiw​i​​ (1≤wi≤10000)(1≤w​i​​≤10000)
第三行输入 nn 个正整数 表示每个物品的价值 viv​i​​ (1≤vi≤10000)(1≤v​i​​≤10000)

输出

输出一个数，表示可装入背包的最大容量时的价值（结果保留两位小数）

样例输入1         复制

150 7
35 30 60 50 40 10 25 
10 40 30 50 35 40 30 

样例输出1         复制

190.62

可以使用贪心算法来解决背包问题，计算出背包的最大价值。代码中使用一个结构体数组 k 来存储物品的重量、价值和单位重量价值，然后根据单位重量价值的降序对物品进行排序。接着，从单位重量价值最高的物品开始，依次将物品放入背包，直到背包的容量不足以放下下一个物品为止。最后，计算出背包中物品的总价值并输出。

不加注释版(AC)

#include <bits/stdc++.h>
using namespace std;
struct node{double a,b,c;
}k[99999];
int n,m;
double mx=0;
bool cmp(node x, node y){return x.c > y.c;
}
int main() {cin>>n>>m;for(int i=0;i<m;i++){cin>>k[i].a;}for(int i=0;i<m;i++){cin>>k[i].b;k[i].c=k[i].b/k[i].a;}sort(k,k+m,cmp);for(int i=0;i<m;i++){if(n-k[i].a>=0){n-=k[i].a;mx+=k[i].b;}else{mx+=k[i].c*n;break;}}cout << fixed << setprecision(2) << mx<< endl;return 0;
}

加注释版（AC）

#include <bits/stdc++.h>
using namespace std;struct node {double a, b, c; // 物品的重量、价值和单位重量价值
};bool cmp(node x, node y) {return x.c > y.c; // 按照单位重量价值的降序排序
}int main() {int n, m;cin >> n >> m; // 输入背包容量和物品个数node k[m]; // 创建存储物品的数组// 输入每个物品的重量for (int i = 0; i < m; i++) {cin >> k[i].a;}// 输入每个物品的价值，并计算单位重量价值for (int i = 0; i < m; i++) {cin >> k[i].b;k[i].c = k[i].b / k[i].a;}sort(k, k + m, cmp); // 按照单位重量价值的降序排序double mx = 0; // 记录背包中物品的总价值// 依次将物品放入背包，直到背包容量不足for (int i = 0; i < m; i++) {if (n - k[i].a >= 0) {n -= k[i].a; // 将物品放入背包mx += k[i].b; // 更新总价值} else {mx += k[i].c * n; // 将物品的一部分放入背包break;}}cout << fixed << setprecision(2) << mx << endl; // 输出背包中物品的总价值return 0;
}