77 lines
2.4 KiB
C++
77 lines
2.4 KiB
C++
#include<bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int N = 110;
|
||
|
||
struct Node {
|
||
int weight; //重量
|
||
int volume; //体积
|
||
int money; //让利金额
|
||
} a[N];
|
||
|
||
/**
|
||
测试用例
|
||
10 9 4
|
||
8 3 6
|
||
5 4 5
|
||
3 7 7
|
||
4 5 4
|
||
*/
|
||
|
||
//在取得最大让利金额的时候，到底是拿了哪些商品？
|
||
string s[N][N][N];
|
||
|
||
//三维数组用来装最大优惠结果集
|
||
int yh[N][N][N];
|
||
|
||
int main() {
|
||
//w:可以提起 w 单位重量的东西，
|
||
//v:有一个能装v个单位体积的购物袋
|
||
//n:为商品种类数
|
||
int w, v, n;
|
||
cin >> w >> v >> n;
|
||
for (int i = 1; i <= n; i++) cin >> a[i].weight >> a[i].volume >> a[i].money;
|
||
|
||
//三维数组初始化
|
||
for (int i = 0; i <= n; i++) {
|
||
for (int j = 0; j <= w; j++) {
|
||
for (int k = 0; k <= v; k++) {
|
||
yh[i][j][k] = 0;
|
||
//初始化
|
||
s[i][j][k] = "";
|
||
}
|
||
}
|
||
}
|
||
//遍历每个种类
|
||
for (int i = 1; i <= n; i++) {
|
||
//从1开始，一个一个去增加重量尝试
|
||
for (int j = 1; j <= w; j++) {
|
||
//从1开始，一个个去增加体积尝试
|
||
for (int k = 1; k <= v; k++) {
|
||
//yh[0]是没有意义的，就是为了数学好算,也就是在未引入i时的上一个最优解
|
||
int bn = yh[i - 1][j][k];
|
||
int x = 0;
|
||
//如果剩余的重量和体积都够用的时候,尝试拿当前物品
|
||
if (j >= a[i].weight && k >= a[i].volume)
|
||
x = yh[i - 1][j - a[i].weight][k - a[i].volume] + a[i].money;
|
||
|
||
if (x > bn) { //如果拿了比不拿价值大,就拿这个物品
|
||
yh[i][j][k] = x;
|
||
//同时记录拿了这个物品
|
||
s[i][j][k] = s[i - 1][j - a[i].weight][k - a[i].volume] + " " + (char) (i + '0');
|
||
} else {
|
||
//否则记录当前重量和体积的最优策略是不拿
|
||
yh[i][j][k] = bn;
|
||
//同时记录不拿当前物品,保持和之前一样的物品列表
|
||
s[i][j][k] = s[i - 1][j][k];
|
||
}
|
||
}
|
||
}
|
||
}
|
||
//输出
|
||
cout << yh[n][w][v] << endl; //小惠能够得到的最大让利金额
|
||
string str = s[n][w][v]; //依次为从小到大排列的商品序号
|
||
cout << str.substr(1, str.size() - 1);
|
||
}
|
||
|