`

【二维分组背包记录路径】暗黑破坏神

阅读更多
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;
}
1
1
分享到:
评论

相关推荐

    代码 基于蚁群算法的二维路径规划代码

    代码 基于蚁群算法的二维路径规划代码代码 基于蚁群算法的二维路径规划代码代码 基于蚁群算法的二维路径规划代码代码 基于蚁群算法的二维路径规划代码代码 基于蚁群算法的二维路径规划代码代码 基于蚁群算法的二维...

    二维费用背包问题

    二维费用背包问题是一种扩展自传统背包问题的优化算法模型,主要应用于物品选择和资源分配的决策问题。在经典的背包问题中,每件物品只有一个费用,而在二维费用背包问题中,每件物品有两个不同的费用,通常称为代价...

    基于蚁群算法的二维路径规划算法

    二维路径规划是计算机科学和人工智能领域中的一个重要课题,特别是在机器人导航、物流配送、地图寻路等领域有着广泛应用。蚁群算法(Ant Colony Optimization, ACS)是一种模拟自然界蚂蚁寻找食物过程中路径选择行为...

    蚁群算法的二维路径规划

    在这个特定的场景——“蚁群算法的二维路径规划”中,我们关注的是如何利用这种算法为机器人规划在二维空间中的最优路径。 一、蚁群算法基础 1. **信息素概念**:蚂蚁在行走过程中会留下一种称为信息素的化学物质...

    蚁群算法进行二维路径规划.zip

    《蚁群算法在二维路径规划中的应用》 二维路径规划是计算机科学与工程领域中一个重要的研究方向,尤其是在机器人导航、物流配送、自动驾驶等场景中有着广泛应用。在这些领域,寻找最优路径以达到效率最大化或者资源...

    算法相关-二维迷宫最短路径求解

    二维迷宫最短路径求解是计算机科学中的一个重要问题,主要涉及到算法设计和实现。在这个问题中,我们通常会利用图论和搜索算法来寻找从起点到终点的最短路径。VC(Visual C++)是一种常用的编程环境,用于编写控制台...

    MATLAB基于蚁群算法的二维路径规划算法

    在这个特定的项目中,“MATLAB基于蚁群算法的二维路径规划算法”是利用ACO来寻找二维空间内两点之间的最短路径。 一、蚁群算法基础 蚁群算法是一种模拟进化算法,它通过模拟蚂蚁在寻找食物过程中留下的信息素轨迹来...

    基于蚁群算法的二维路径规划算法.zip_path planning_tsp 障碍_网络规划_蚁群算法二维_蚁群路径

    基于蚁群算法的二维网络路径规划算法,带有障碍物的TSP问题,可运行

    二维A*算法路径规划matlab代码

    以复杂岛屿地图为例,做了二维A*路径规划。代码为MATLAB代码,解压后可以直接运行。文件夹内AstarCSDN为主文件,TrunToGridMap为地图转栅格文件,child_nodes_cal为计算子节点的函数,1234d.jpg为地图图片。

    基于ACO蚁群优化的二维路径规划算法matlab仿真,含仿真操作录像

    2.领域:二维路径规划 3.内容:基于ACO蚁群优化的二维路径规划算法matlab仿真。 %% 蚁群算法参数初始化 pathCount = length(path)-2; %经过线段数量 pheCacuPara=2; %信息素计算参数 pheThres = 0.8; %信息素选择...

    基于蚁族算法的二维路径规划算法

    二维路径规划是机器人学、计算机科学以及人工智能领域中的一个重要课题,其目标是在复杂环境中找到从起点到终点的最短或最优路径。蚁群算法(Ant Colony Optimization, ACO)是一种模拟自然界蚂蚁寻找食物路径的优化...

    pso 二维路径规划.zip

    《基于PSO的二维路径规划在MATLAB中的实现》 粒子群优化算法(Particle Swarm Optimization, PSO)是一种源于生物社会行为的优化方法,广泛应用于解决复杂问题的全局寻优,如路径规划、机器学习等领域。本文将详细...

    113、1272:【例9.16】分组背包--2020.03.31a.pdf

    - **输入数据**:通过循环读取每件物品的重量、价值及其所属组号,并将其存储在二维数组 `a` 中,其中 `a[p][0]` 记录了组号为 `p` 的物品的数量。 - **动态规划计算**:外层循环遍历所有组;中间层循环倒序遍历背包...

    【二维路径规划】基于A星算法求解机器人路径规划matlab代码.zip

    标题中的“二维路径规划”指的是在二维空间内为机器人或移动实体设计一条从起点到终点的有效路径。这种规划通常应用于自动化、无人机、自动驾驶车辆等领域。A星(A*)算法是一种广泛应用的启发式搜索算法,它结合了...

    【路径规划】基于粒子群算法求解二维最短路径matlab源码.zip

    【路径规划】基于粒子群算法求解二维最短路径matlab源码.zip这个压缩包包含了一个使用MATLAB实现的粒子群优化(PSO)算法,用于解决二维空间中的最短路径问题。粒子群优化是一种灵感来源于鸟群飞行行为的全局优化...

    yiqunguihua.zip_matlab 路径_matlab 路径规划_二维 路径规划_路径规划 蚁群

    在本资源中,我们关注的是一个使用Matlab实现的蚁群算法(Ant Colony Optimization, ACO)进行二维路径规划的程序。蚁群算法是一种优化技术,受到蚂蚁寻找食物过程中路径选择行为的启发,常用于解决旅行商问题、网络...

    基于灰狼算法的二维路径规划(matlab)

    本项目聚焦于使用灰狼算法(Grey Wolf Optimizer, GWO)来解决二维空间中的路径规划问题。灰狼算法是一种启发式优化方法,模仿了灰狼群体在自然界中的狩猎行为,具有良好的全局寻优性能。 **灰狼算法(Grey Wolf ...

    二维地震多道记录成图

    地震数据剖面显示程序,能将matlab数据按常规剖面显示(正值部分涂黑,负值部分不变)。 用于应用二维数组,生成地震记录剖面,对于地震模型的模拟数据快速生成剖面很有帮助。

    通过ACO蚁群算法分别实现TSP,二维路径规划,三维路径规划以及栅格地图避障规划仿真+代码操作视频

    2.内容:通过ACO蚁群算法分别实现TSP,二维路径规划,三维路径规划以及栅格地图避障规划仿真+代码操作视频 3.用处:用于通过ACO蚁群算法分别实现TSP,二维路径规划,三维路径规划以及栅格地图避障编程学习 4.指向人群...

Global site tag (gtag.js) - Google Analytics