有个牛牛一起去朋友家吃糖果,第个牛牛一定要吃块糖果.
而朋友家一共只有块糖果,可能不会满足所有的牛牛都吃上糖果。
同时牛牛们有个约定,每一个约定为一个牛牛的编号对,表示第个和第个牛牛是好朋友,他俩要么一起都吃到糖果,要么一起都不吃。
保证每个牛牛最多只出现在一个编号对中。
您可以安排让一些牛牛吃糖果,一些牛牛不吃。
要求使能吃上糖果的牛牛数量最多(吃掉的糖果总量要小于等于),并要满足不违反牛牛们的个约定。
有个牛牛一起去朋友家吃糖果,第个牛牛一定要吃块糖果.
而朋友家一共只有块糖果,可能不会满足所有的牛牛都吃上糖果。
同时牛牛们有个约定,每一个约定为一个牛牛的编号对,表示第个和第个牛牛是好朋友,他俩要么一起都吃到糖果,要么一起都不吃。
保证每个牛牛最多只出现在一个编号对中。
您可以安排让一些牛牛吃糖果,一些牛牛不吃。
要求使能吃上糖果的牛牛数量最多(吃掉的糖果总量要小于等于),并要满足不违反牛牛们的个约定。
第一行个正整数 ,
第二行个正整数 ,
第三行个整数
接下来行,每行两个正整数 ,表示第个牛牛与第个牛牛有约定。
一行一个数字表示最多能吃上糖果的牛牛个数
3 10 5 1 5 1 1 3
2
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背包问题。