猫粮规划
题目描述
到中午了,机器猫要吃猫粮了。
机器猫掏出 $n$ 份食物,第 $i$ 份食物含有的能量为 $w[i]$。机器猫可以吃掉其中一些食物,获得这些食物的能量之和。
机器猫又不想变得太胖又不想变得太瘦,所以指定了一个目标区间 $[l, r]$。显然,可能有很多种选择食物的方式可以达成这个目标,因此机器猫想知道方案总数。
输入格式
第一行,三个正整数 $n, l, r$。
第二行,$n$ 个正整数,表示每一份食物含有的能量 $w[i]$。
输出格式
仅一行,一个整数,表示方案数。
样例 #1
样例输入 #1
4 70 85
10 10 20 50
样例输出 #1
4
提示
样例解释
所有方案如下:
选择食物 1, 2, 4,能量 10+10+50 = 70
选择食物 1, 3, 4,能量 10+20+50 = 80
选择食物 2, 3, 4,能量 10+20+50 = 80
选择食物 3, 4,能量 50+20 = 70
共 4 种方案。
数据规模与约定
对于 $50\%$ 的数据,满足 $n\leq 20$。
对于 $100\%$ 的数据,满足 $n\leq 40, 20\leq w[i] \leq 100, l\leq r \leq 300$。
提示:$w[i]$ 在范围内均匀随机生成。
题解
itertools.combinations(就是暴力枚举) 能过50%测试数据 其余TLE
这个代码不用怎么解释,这个问题说白了就是类组合问题,用python自带标准库暴力枚举遍历,但因为难以进行剪枝,所以极限就是过50%。
python代码
# 输入输出解释
# 4 70 85 4种猫粮,组合能量值介于[70,85]
# 10 10 20 50 猫粮能量值列表
# 输出
# 4 共有4种组合
import itertools
def search(combinations,i):
global ans
for combo in combinations:
sum1=sum(combo)
if l<=sum1<=r:
ans+=1
if combo[-1]==feeds[i-1] and sum1>r:
return 0
return 1
n,l,r=map(int,input().split())
feeds=list(map(int,input().split()))
feeds.sort()
ans=0
for i in range(1,n+1):
combinations=itertools.combinations(feeds,i)
whetherBreak=search(combinations,i)
if whetherBreak==0:
break
print(ans)
# 50% https://www.luogu.com.cn/record/167659007
算法2 dfs AC
该算法树桩遍历顺序手绘,总的来说就是组合n叉树的先序深度优先遍历
为什么要像下面这么写?
那要从二叉树的先序遍历说起(具体见下图)
python 代码
# 输入输出解释
# 4 70 85 4种猫粮,组合能量值介于[70,85]
# 10 10 20 50 猫粮能量值列表
# 输出
# 4 共有4种组合
def dfs(x,current_sum):
global n,l,r,feeds,ans
if r>=current_sum>=l:
ans+=1
if current_sum>r: # 剪枝
return
if x>=n:
return
for i in range(x,n): # 从x开始搜,以免重复
dfs(i+1,current_sum+feeds[i])
n,l,r=map(int,input().split())
feeds=list(map(int,input().split()))
ans=0
dfs(0,0)
print(ans)
讲得真好