算法实验作业 3-3 购物问题

问题描述：

由于换季，某商场推出优惠活动，以超低价格出售若干种商品。但是，商场为避免过分

亏本，规定某些商品不能同时购买，而且每种超低价商品只能买一件。身为顾客的你想获得

最大的实惠，也就是争取节省最多的钱。经过仔细研究过，我们发现，商场出售的超低价商

品中，不存在以下这种情况：

n(3≤n)种商品 c1, c2, c3,…, cn，其中 ci和 ci+1是不能同时购买的（i=1, 2, …,n-1），而

且 c1和 cn也不能同时购买。

编程任务：

请编程计算可以节省的最大金额数。

数据输入：

第 1 行两个整数 K，M（1≤K≤1000），其中 K 表示超低价商品数，K 种商品的编号依

次为 1,2, …,K；M 表示不能同时购买的商品对数。

接下来 K 行，第 i 行有一个整数 Xi 表示购买编号为 i 的商品可以节省的金额（1≤Xi

≤100）。

再接下来 M 行，每行两个数 A 和 B，表示 A 和 B 不能同时购买，1≤A≤K，1≤B≤K，A

≠B。

结果输出

输出计算出的能节省的最大金额数。

输入文件示例 输出文件示例

input.txt output.txt

3 1

1

1

1

1 2

2-算法实验作业 3-3 购物问题

问题描述：

由于换季，某商场推出优惠活动，以超低价格出售若干种商品。但是，商场为避免过分

亏本，规定某些商品不能同时购买，而且每种超低价商品只能买一件。身为顾客的你想获得

最大的实惠，也就是争取节省最多的钱。经过仔细研究过，我们发现，商场出售的超低价商

品中，不存在以下这种情况：

n(3≤n)种商品 c1, c2, c3,…, cn，其中 ci和 ci+1是不能同时购买的（i=1, 2, …,n-1），而

且 c1和 cn也不能同时购买。

编程任务：

请编程计算可以节省的最大金额数。

数据输入：

第 1 行两个整数 K，M（1≤K≤1000），其中 K 表示超低价商品数，K 种商品的编号依

次为 1,2, …,K；M 表示不能同时购买的商品对数。

接下来 K 行，第 i 行有一个整数 Xi 表示购买编号为 i 的商品可以节省的金额（1≤Xi

≤100）。

再接下来 M 行，每行两个数 A 和 B，表示 A 和 B 不能同时购买，1≤A≤K，1≤B≤K，A

≠B。

结果输出

输出计算出的能节省的最大金额数