赞
踩
打包
总时间限制: 10000ms 单个测试点时间限制: 1000ms 内存限制: 65536kB
描述
假如你现在拿到了许多的礼物,你要把这些礼物放进袋子里。你只有一个最多能装下V体积物品的袋子,你不能全部放进去。因为你拿不动那么重的东西。你估计你能拿的最大重量为G。现在你了解每一个物品的完美值、重量和体积,你当然想让袋子中装的物品的完美值总和最大,如何装?
输入
第一行V和G表示最大重量和体积
第二行N表示拿到N件礼物
第3到N+2行表示各礼物的完美值、重量和体积
输出
物品的完美值总和
样例输入
6 5
4
10 2 2
20 3 2
40 4 3
30 3 3
样例输出
50
题解思路:在基本背包基础上使用二维数组来解决(每个维度分别代表体积与体重)
源代码:
改进算法
- #include<stdio.h>
- #include<stdlib.h>
- struct Cell
- {
- int v;
- int g;
- int wmz;
- };
- Cell *sz2(int a)
- {
- return (Cell*)malloc(a*sizeof(Cell));
- }
- int **sz(int a, int b)// 前下标a:体积 后下标b:重量
- {
- int **p;
- int i=0, j;
- p=(int**)malloc(a*sizeof(int*));
- for(i=0;i&l
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。