http://openoj.awaysoft.com/JudgeOnline/problem.php?id=1634
暗黑破坏神
Description
无聊中的小x玩起了Diablo I...
游戏的主人公有n个魔法
每个魔法分为若干个等级,第i个魔法有p[i]个等级(不包括0)
每个魔法的每个等级都有一个效果值,一个j级的i种魔法的效果值为w[i][j]
魔法升一级需要一本相应的魔法书
购买魔法书需要金币,第i个魔法的魔法书价格为c[i]
而小x只有m个金币(好孩子不用修改器)
你的任务就是帮助小x决定如何购买魔法书才能使所有魔法的效果值之和最大
开始时所有魔法为0级 效果值为0
Input
第一行 用空格隔开的两个整数n(0<n<=100) m(0<m<=500)
以下n行 描述n个魔法
第i+1行描述 第i个魔法 格式如下(0<p[i]<=50, 0<c[i]<=10)
c[i] p[i] w[i][1] w[i][2] ... w[i][p[i]]
Output
第一行输出一个整数,即最大效果值。(保证输入数据和最终结果在longint范围内)
以后n行输出你的方案:
第i+1行有一个整数v[i] 表示你决定把第i个魔法学到v[i]级
如果有多解 输出花费金币最少的一组
如果还多解 输出任意一组
Sample Input
3 10
1 3 1 2 2
2 3 2 4 6
3 3 2 1 10
Sample Output
11
1
0
3
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <iomanip>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <ctype.h>
using namespace std;
#define inf 0x3fffffff
int dp[105][505], w[105], M, num, mark[105][505], v[105], c[105];
void gp1_pack (int i, int cost) //二维分组背包
{
int j, k;
for (j = 1; j <= M; j++)
{
for (k = 0; k <= num && j >= k*cost; k++)
{
if (dp[i][j] < dp[i-1][j-k*cost] + w[k])
{
dp[i][j] = dp[i-1][j-k*cost] + w[k];
mark[i][j] = k; //记录魔法级数【k:第i组的第k个物品】
}
}
}
}
int main()
{
int n, i, j, maxs, vj;
while (~scanf ("%d%d", &n, &M))
{
w[0] = 0;
for (i = 1; i <= n; i++)
{
scanf ("%d%d", c+i, &num);
for (j = 1; j <= num; j++)
scanf ("%d", w+j);
gp1_pack (i, c[i]); //每一组进行一次背包
}
maxs = 0;
for (j = M; j >= 0; j--) //寻找花费最小价值最大的路径终点
if (maxs <= dp[n][j])
maxs = dp[n][j], vj = j;
j = vj; //关键终点
for (i = n; i > 0; i--)
{
v[i] = mark[i][j]; //记录路径
j = j - c[i] * v[i]; //返回上一层
}
printf ("%d\n", maxs);
for (i = 1; i <= n; i++) //路径输出
printf ("%d\n", v[i]);
}
return 0;
}
分享到:
相关推荐
代码 基于蚁群算法的二维路径规划代码代码 基于蚁群算法的二维路径规划代码代码 基于蚁群算法的二维路径规划代码代码 基于蚁群算法的二维路径规划代码代码 基于蚁群算法的二维路径规划代码代码 基于蚁群算法的二维...
二维费用背包问题,用于算法的背包问题的延伸
用VC编写的控制控制台程序,求二维迷宫的最短路径。
基于蚁群算法的二维网络路径规划算法,带有障碍物的TSP问题,可运行
以复杂岛屿地图为例,做了二维A*路径规划。代码为MATLAB代码,解压后可以直接运行。文件夹内AstarCSDN为主文件,TrunToGridMap为地图转栅格文件,child_nodes_cal为计算子节点的函数,1234d.jpg为地图图片。
蚁群算法的二维路径规划,可以用在机器人的路径规格中,程序详细
基于蚁群算法的二维路径规划算法,结合具体的案例给出了程序分析
蚁群算法进行二维路径规划的MATLAB,非常值得学习学习。
MATLAB 用基本蚁群算法进行二维路径规划,后面还有画图显示。
2.领域:二维路径规划 3.内容:基于ACO蚁群优化的二维路径规划算法matlab仿真。 %% 蚁群算法参数初始化 pathCount = length(path)-2; %经过线段数量 pheCacuPara=2; %信息素计算参数 pheThres = 0.8; %信息素选择...
2.内容:通过ACO蚁群算法分别实现TSP,二维路径规划,三维路径规划以及栅格地图避障规划仿真+代码操作视频 3.用处:用于通过ACO蚁群算法分别实现TSP,二维路径规划,三维路径规划以及栅格地图避障编程学习 4.指向人群...
17.基于蚁群算法的二维路径规划算法.zip17.基于蚁群算法的二维路径规划算法.zip17.基于蚁群算法的二维路径规划算法.zip17.基于蚁群算法的二维路径规划算法.zip17.基于蚁群算法的二维路径规划算法.zip17.基于蚁群算法...
二维费用背包
基于蚁族算法的二维路径规划算法,可以用于机器人的路径规划问题,寻找最优路径。
matlab蚁群算法二维路径规划
该程序是基于蚁群算法的二维路径规划算法程序,对二维路径规划非常有用,有详细的程序说明介绍
基于灰狼算法的二维路径规划(matlab)
模拟退火算法解决二维路径规划路径寻优问题,这里上传主函数, 代码并非本人所写,可能版本不同运行时需要细微修改。在于解决路径规划的路径寻优问题,,需要打开后自行保存运行
使用matlab软件进行仿真,建立20*20的二维栅格网络,采用引入精英蚂蚁的蚁群算法进行路径规划,使用GUI界面进行人机交互,可自定义障碍物,对蚂蚁起终点位置坐标、蚂蚁数量、精英蚂蚁的数量、信息素因子、迭代次数等...
本程序基于MATLAB语言,主要实现的是路径规划的问题,实现二维环境下对运动路径的最优规划。