牛牛准备参加学校组织的春游, 出发前牛牛准备往背包里装入一些零食, 牛牛的背包容量为w。
牛牛家里一共有n袋零食, 第i袋零食体积为v[i]。
牛牛想知道在总体积不超过背包容量的情况下,他一共有多少种零食放法(总体积为0也算一种放法)。
输入包括两行
第一行为两个正整数n和w(1 <= n <= 30, 1 <= w <= 2 * 10^9),表示零食的数量和背包的容量。
第二行n个正整数v[i](0 <= v[i] <= 10^9),表示每袋零食的体积。
输出一个正整数, 表示牛牛一共有多少种零食放法。
3 10 1 2 4
8
三种零食总体积小于10,于是每种零食有放入和不放入两种情况,一共有2*2*2 = 8种情况。
_, w = input("").split() w = int(w) arr = [int(i) for i in input("").split()] from functools import lru_cache @lru_cache() def process(ind, rest): if rest < 0: return 0 if ind == len(arr): return 1 return process(ind + 1, rest) + process(ind + 1, rest - arr[ind]) print(process(0, w))
def main(): # get input n, w = map(int, input().split()) v = list(map(int, input().split())) assert len(v) == n, "invalid input !" # 当全部零食都能装下,也就是不需要剪枝,那么递归耗时太大,可以直接用公式计算 if sum(v) <= w: print(2 ** n) return # backtrack function global cnt cnt = 0 def backtrack(s=0, res=[]): if sum(res[:]) <= w: global cnt cnt += 1 for i in range(s,n): res.append(v[i]) backtrack(i+1, res) res.pop() # get ans backtrack() print(cnt) if __name__ == "__main__": main()
#include<iostream> #include<algorithm> using namespace std; void count(long long int v[], int& res, long long int w, int right); int main(){ int n; long long int w; cin>>n>>w; long long int v[n]; for(int i=0;i<n;i++) cin>>v[i]; int res=1; sort(v,v+n); long long int sum = 0; for(int i=0;i<n;i++) sum += v[i]; if(sum<=w) res = pow(2,n); else count(v,res,w,n); cout<<res<<endl; } void count(long long int v[], int& res, long long int w, int right){ //int pos = right; //while(v[pos]>w) pos--; int pos = upper_bound(v,v+right,w) - v; pos--; for(int i=pos;i>=0;i--){ res++; if(i-1>=0 && w-v[i]>0) count(v,res,w-v[i],i); } }