我要招人

去企业版

首页 > 试题广场 >

牛牛们吃糖果

[编程题]牛牛们吃糖果

热度指数：2187 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有 $\mathit n$ 个牛牛一起去朋友家吃糖果，第 $\mathit i$ 个牛牛一定要吃 $a_i$ 块糖果.

而朋友家一共只有 $\mathit m$ 块糖果，可能不会满足所有的牛牛都吃上糖果。

同时牛牛们有 $\mathit k$ 个约定，每一个约定为一个牛牛的编号对 $(i,j)$ ，表示第 $\mathit i$ 个和第 $\mathit j$ 个牛牛是好朋友，他俩要么一起都吃到糖果，要么一起都不吃。

保证每个牛牛最多只出现在一个编号对中。

您可以安排让一些牛牛吃糖果，一些牛牛不吃。

要求使能吃上糖果的牛牛数量最多（吃掉的糖果总量要小于等于 $\mathit m$ ），并要满足不违反牛牛们的 $\mathit k$ 个约定。

输入描述:

第一行 $\text 2$ 个正整数 $n,m$ ， $1\leq n\leq 10^3,1\leq m \leq 10^3$

第二行 $\mathit n$ 个正整数 $a_1,a_2,\dots,a_n$ , $1\leq a_i \leq 10^6$

第三行 $\text 1$ 个整数 $k,0 \leq k \leq \frac{n}{2}$

接下来 $\mathit k$ 行，每行两个正整数 $i,j$ ，表示第 $\mathit i$ 个牛牛与第 $\mathit j$ 个牛牛有约定。

输出描述:

一行一个数字表示最多能吃上糖果的牛牛个数

示例1

输入

输出

算法知识视频讲解

Python

海布里到酋长

n,m = map(int,input().split())
eat = list(map(int,input().split()))
k = int(input())
l = []
for i in range(k):
    l.append(list(map(int,input().split())))
value = []
weight = []
inbeer = []
for link in l:
    inbeer.append(link[0]-1)
    inbeer.append(link[1]-1)
    weight.append(eat[link[0]-1]+eat[link[1]-1])
    value.append(2)

for idx,num in enumerate(eat):
    if idx not in inbeer:
        value.append(1)
        weight.append(num)
dp = [0]*(m+1)


#先遍历物品，在遍历背包

for i in range(len(weight)):
    for j in range(m,weight[i]-1,-1):
        dp[j] = max(dp[j],dp[j-weight[i]]+value[i])

print(dp[-1])

感觉难点在输入输出数据啊，转化为0-1背包问题。

糖m表示背包的最大容量，物品的价值是个数即1或2，物品的重量就是所需吃的糖数

发表于 2022-04-01 11:44:35 回复(0)

Python

牛客60529366号

参照上面的dalao写的python3

n, m = map(int, input().split())

a = list(map(int, input().split()))
v = [1] * n
k = int(input())
for _ in range(k):
x, y = (input().split())
x = int(x) - 1
y = int(y) - 1
a[x] += a[y]
v[x] += 1
v[y] = 0

opt = [0] * (m+1)
for i in range(n):
if v[i] == 0:
continue
for j in range(m, a[i]-1, -1):
opt[j] = max(opt[j], opt[j-a[i]] + v[i])

print(opt[-1])

编辑于 2021-08-01 23:23:05 回复(0)