牛牛准备参加学校组织的春游, 出发前牛牛准备往背包里装入一些零食, 牛牛的背包容量为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种情况。
想了一下只能用dfs
然后算法如下
最开始的时候会超出运行时间 原因是未考虑 当所有零食的重量之和小于背包的容量的情况和任意一个零食的重量都大于背包的容量的情况。
#include <iostream> long long int v[31]; int dfs(long long int w,long long int n){ if(w < 0){ return 0; } if(n <= 0 && w >= 0){ return 1; } return dfs(w - v[n-1],n-1) + dfs(w,n-1); } int main(){ long long int n,w,real_n; std::cin >> n >> w; real_n = n; long long int value; long long int sum = 0; int index = 0; for(int i=0;i<n;i++){ std::cin >> value; if(value > w){ real_n--; continue; } sum+=value; v[index] = value; index++; } if(sum <=w){ std::cout << (1 << real_n) << std::endl; }else{ std::cout << dfs(w,real_n) << std::endl; } return 0; }
#include <bits/stdc++.h> using namespace std; typedef long long ll; int n, count1 = 0; ll a[40], w; vector<ll> v; void dfs1(int i, int t, ll now) { if(now > w) return; if(i == t) { v.push_back(now); return;} dfs1(i + 1, t, now + a[i]); dfs1(i + 1, t, now); } void dfs2(int i, ll now) { if(now > w) return; if(i == n) { count1 += upper_bound(v.begin(), v.end(), w - now) - v.begin(); return; } dfs2(i + 1, now + a[i]); dfs2(i + 1, now); } int main() { cin >> n >> w; for(int i = 0; i < n; i++) cin >> a[i]; int t = n / 2; dfs1(0, t, 0); sort(v.begin(), v.end()); dfs2(t, 0); cout << count1 << endl; return 0; } 算法 : 折半枚举. 复杂度 : O(n * 2 ^ (n / 2)) (出题人数据没造好)
import java.util.Map; import java.util.Scanner; import java.util.TreeMap; public class Main { // 根据数据量的规模,选择用分治来处理 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int bag = sc.nextInt(); int[] arr = new int[N]; for (int i = 0; i < arr.length; i++) { arr[i] = sc.nextInt(); } long ways = ways(arr, bag); System.out.println(ways); sc.close(); } public static long ways(int[] arr, int bag) { // process过程定义好,那么在当前函数中就应该这样调用: // arr 30 // process(arr, 0, 14, 0, bag, map) // process(arr, 15, 29, 0, bag, map) if (arr == null || arr.length == 0) { return 0; } if (arr.length == 1) { return arr[0] <= bag ? 2 : 1; } // 分治算法 int mid = (arr.length - 1) >> 1; TreeMap<Long, Long> lmap = new TreeMap<>(); // 只从左侧选取得到的符合题意的方法数 long ways = process(arr, 0, mid, 0, bag, lmap); TreeMap<Long, Long> rmap = new TreeMap<>(); // 只从右侧选取得到的符合题意的方法数(和左侧的加起来) ways += process(arr, mid + 1, arr.length - 1, 0, bag, rmap); // 两张表lmap和rmap分别已经收集好左右两部分所有符合条件sum及其方法数 // 此时把右侧表建立一个前缀和表出来 TreeMap<Long, Long> rpre = new TreeMap<>(); long pre = 0; for (Map.Entry<Long, Long> entry : rmap.entrySet()) { pre += entry.getValue(); rpre.put(entry.getKey(), pre); } // 右侧的前缀和表已经建好 // 接下来左侧严格按照表中每一个数据来和右侧符合条件的数据相结合 for (Map.Entry<Long, Long> entry : lmap.entrySet()) { long lweight = entry.getKey(); long lways = entry.getValue(); // 左侧当前的零食大小是lweight,右侧在不超过bag的情况下最大的装载量是floor Long floor = rpre.floorKey(bag - lweight);// floorKey()方法意即找到小于等于该数且离他最近的那个数 // 右侧只要零食大小不超过floor,都视为符合条件,找出他们的方法数 if (floor != null) { long rways = rpre.get(floor); ways += lways * rways; } } return ways + 1; } // 从index出发,到end结束 // 之前的选择,已经形成的累加和为sum // 零食[index...end]自由选择,出来的所有累加和不能超过bag,每一种累加和对应的方法数,填在map里 // 最后不能什么货都没选(最后直接在总方法数上加1即可表示这种情况) // 举例: // [3,3,3,3] bag=6 // 0 1 2 3 // - - - - 0 -> (0 : 1) // - - - $ 3 -> (0 : 1) (3, 1) // - - $ - 3 -> (0 : 1) (3, 2) public static long process(int[] arr, int index, int end, long sum, int bag, TreeMap<Long, Long> map) { if (sum > bag) { return 0; } // sum <= bag if (index > end) { if (sum != 0) { if (!map.containsKey(sum)) { map.put(sum, 1L); } else { map.put(sum, map.get(sum) + 1); } return 1; } else { // sum==0 说明什么都没选,这种情况不计数 return 0; } } // sum < bag && index <= end(还有货) // 1) 不要当前index位置的货 long ways = process(arr, index + 1, end, sum, bag, map); // 2) 要当前index位置的货 ways += process(arr, index + 1, end, sum + arr[index], bag, map); return ways; } }
#include<bits/stdc++.h> using namespace std; long long n,w,v[50],ans=0; long long Pow(long long a,long long b) //快速幂 { long long r=1; while(b) { if(b&1) r*=a; a*=a; b>>=1; } return r; } void dfs(long long m,long long s) //放m号,之前体积为s { if(s>w) return ; if(m==n) { ans++; return ; } dfs(m+1,s+v[m]); //下次放m+1号,之前体积为s+v[m] dfs(m+1,s); return ; } int main() { long long i; long long sum=0; cin>>n>>w; //数量和背包的容量 for(i=0;i<n;i++) { cin>>v[i]; sum+=v[i]; } if(sum<=w) cout<<Pow(2,n)<<endl; else { dfs(0,0); //下次放0号,之前体积为0 cout<<ans<<endl; } return 0; }
借鉴一下DFS#include<bits/stdc++.h>using namespace std;long long v[40];int n;long long ans=0,w;void dfs(int t,long long sum){ans++;if(t==n-1){return ;}for(int i=t+1;i<n;i++){if(sum+v[i]<=w){dfs(i,sum+v[i]);}}}int main(){//long long w;cin>>n>>w;long long sum=0;for(int i=0;i<n;i++){cin>>v[i];sum+=v[i];}if(sum<=w){ans=1<<n;//根据题目,0个也算进去,那就正好是左移n位}else{dfs(-1,0);}cout<<ans<<endl;return 0;}
Map.prototype.floorKey = function(key) { let map = this; let ans = null; for(let k of map.keys()) { if(k > key) { break; } else { ans = k; } } return ans; } // 根据数据量描述,2^30>10^8,采用分而治之的思路 function ways(arr, bag) { let len = arr.length; if(arr == null || len == 0) { return 0; } if(len == 1) { return arr[0] <= bag ? 2: 1; } let mid = (len - 1) >> 1; let lmap = new Map(); let ways = process(arr, 0, 0, mid, bag, lmap); let rmap = new Map(); ways += process(arr, mid + 1, 0, len - 1, bag, rmap); // 对rmap进行手动排序,以模拟TreeMap,这里先不用手动实现有序表,太冗长 rmap = new Map([...rmap.entries()].sort((a, b) => a[0] - b[0])); let rpre = new Map(); let pre = 0; for(let [key, value] of rmap.entries()) { pre += value; rpre.set(key, pre); // 方法前缀和map } for(let [lweight, lways] of lmap.entries()) { let floor = rpre.floorKey(bag - lweight); if(floor != null) { let rways = rpre.get(floor); ways += lways * rways; } } return ways + 1; // process中没考虑都不选的情况,所以方法加1 } function process(arr, index, w, end, bag, map) { if(w > bag) { return 0; } if(index > end) { if(w != 0) { if(!map.has(w)) { map.set(w, 1); } else { map.set(w, map.get(w) + 1); } return 1; } else { return 0; } } else { let ways = process(arr, index + 1, w, end, bag, map); ways += process(arr, index + 1, w + arr[index], end, bag, map); return ways; } } // 牛客js-v8 处理输入输出 let line1 = readline(); let line2 = readline(); let [n, w] = line1.split(' ').map(x => +x); let v = line2.split(' ').map(x => +x); let res = ways(v, w); print(res);
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int bag = sc.nextInt(); int[] arr = new int[N]; for (int i = 0; i < arr.length; i++) { arr[i] = sc.nextInt(); } long ways = ways(arr, bag); System.out.println(ways); sc.close(); } /** * 分治统计有多少种零食的拿法。 */ private static long ways(int[] arr, int bag) { int N = arr.length; int mid = arr.length-1 >> 1; SBTSet<Long> leftSet = new SBTSet<>(); process(arr, bag, 0, mid, 0L,leftSet); SBTSet<Long> rightSet = new SBTSet<>(); process(arr, bag, mid+1, arr.length-1, 0L, rightSet); int ans = 0; for (int i = 0; i < leftSet.size(); i++) { Long leftWeight = leftSet.getIndexKey(i); ans += rightSet.lessEqualsCount(bag - leftWeight); } return ans; } /** * 当前来到i位置,背包内放入了preSum体积的零食, * 将i..end的所有选择后的体积放入set,但要求总体积不能超过bag * 如果当前来到end+1位置,set添加preSum后返回。 * 尝试不拿当前位置零食,递归调用(i+1, preSum) * 如果arr[i]+preSum<=bag, 递归调用(i+1, preSum+arr[i]) */ private static void process(int[] arr, int bag, int i, int end, Long preSum, SBTSet<Long> set) { if(i == end+1){ set.put(preSum); return; } process(arr, bag, i+1,end, preSum, set); if(arr[i]+preSum<=bag){ process(arr, bag, i+1,end, preSum+arr[i], set); } } public static class SBTNode<K extends Comparable<K>>{ public K key; public int all; public int size; public SBTNode l; public SBTNode r; public SBTNode(K k){ key = k; size = 1; all = 1; } } public static class SBTSet<K extends Comparable<K>>{ private SBTNode<K> root; public int size(){ return getAll(root); } /** * 放入一个数据。 */ public void put(K key){ root = add(root, key); } /** * 在cur树上新增节点,值为key。 */ private SBTNode<K> add(SBTNode<K> cur, K key) { if(cur==null) return new SBTNode<>(key); cur.all++; if(key.compareTo(cur.key)==0) return cur; if(key.compareTo(cur.key)<0){ cur.l = add(cur.l, key); }else { cur.r = add(cur.r, key); } cur.size = getSize(cur.l)+getSize(cur.r)+1; return maintain(cur); } /** * 调整cur节点的平衡性并返回新节点。 * */ private SBTNode<K> maintain(SBTNode<K> cur) { int ls = getSize(cur.l); int lls = 0; int lrs = 0; if(cur.l != null){ lls = getSize(cur.l.l); lrs = getSize(cur.l.r); } int rs = getSize(cur.r); int rrs = 0; int rls = 0; if(cur.r != null){ rrs = getSize(cur.r.r); rls = getSize(cur.r.l); } if(lls>rs){ cur = rightRotate(cur); cur.r = maintain(cur.r); cur = maintain(cur); }else if(lrs>rs){ cur.l = leftRotate(cur.l); cur = rightRotate(cur); cur.l = maintain(cur.l); cur.r= maintain(cur.r); cur = maintain(cur); }else if(rrs>ls){ cur = leftRotate(cur); cur.l = maintain(cur.l); cur = maintain(cur); }else if(rls>ls){ cur.r = rightRotate(cur.r); cur = leftRotate(cur); cur.l = maintain(cur.l); cur.r = maintain(cur.r); cur = maintain(cur); } return cur; } /** * 左旋 */ private SBTNode<K> leftRotate(SBTNode<K> cur) { int same = cur.all - getAll(cur.l) - getAll(cur.r); SBTNode<K> right = cur.r; cur.r = right.l; right.l = cur; right.size = cur.size; cur.size = getSize(cur.l)+getSize(cur.r)+1; right.all = cur.all; cur.all = getAll(cur.l)+getAll(cur.r)+same; return right; } private int getAll(SBTNode<K> cur) { return cur==null?0:cur.all; } /** * 右旋 */ private SBTNode<K> rightRotate(SBTNode<K> cur) { int same = cur.all - getAll(cur.l) - getAll(cur.r); SBTNode left = cur.l; cur.l = left.r; left.r = cur; left.size = cur.size; cur.size = getSize(cur.l)+getSize(cur.r)+1; left.all = cur.all; cur.all = getAll(cur.l)+getAll(cur.r)+same; return left; } private int getSize(SBTNode cur) { return cur==null?0:cur.size; } /** * 返回小于等于指定值的个数。 * 从root开始向下滑。 * 等于返回答案。 * 向右滑收集答案。 * 向左滑不收集。 */ public int lessEqualsCount(K key){ SBTNode<K> cur = root; int ans = 0; while (cur!=null){ if(key.compareTo(cur.key)==0) return ans+cur.all-getAll(cur.r); if(key.compareTo(cur.key)<0){ cur = cur.l; }else { ans += cur.all-getAll(cur.r); cur = cur.r; } } return ans; } /** * 返回排序后位于指定位置的key * 检查key是否超出集合范围。 * 从root向下滑。 * 如果小于左树all范围,来到左树找。 * 如果大于等于cur.all-右树.all,去右树找。 * 否则,返回当前值。 */ public K getIndexKey(int index){ if(index<0 || index>=getAll(root)) throw new RuntimeException("out of range"); return getIndex(root, index).key; } /** * 返回cur树上的第k个节点。 */ private SBTNode<K> getIndex(SBTNode<K> cur, int index){ if(index<getAll(cur.l)){ return getIndex(cur.l, index); }else if(index >= cur.all-getAll(cur.r)){ return getIndex(cur.r, index-(cur.all-getAll(cur.r))); }else { return cur; } } } }
#python #思路:大于背包的过滤掉,背包很大的时候直接求幂,其他情况dfs N,W = map(int,input().split()) nums = list(map(int,input().split())) def judgge(x): return x<=W nums = list(filter(judgge,nums)) N = len(nums) total = sum(nums) count = 0 def dfs(t,sum): global count if sum>W: return if t==N: count+=1 return dfs(t+1,sum+nums[t]) dfs(t + 1, sum) return if total<=W: print(2**N) else: dfs(0,0)# 第i号物品,当前重量 print(count)
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc =new Scanner(System.in); int n=sc.nextInt(); int w=sc.nextInt(); int[] v=new int[n+1]; for(int i=1;i<=n;i++) { v[i]=sc.nextInt(); } //初始化 int[][] dp=new int[n+1][w+1] ; // for(int i=0;i<n+1;i++) { // for(int j=0;j<w+1;j++) { // dp[i][j]=1; // } // } int res=0; dp[1][w]=1; for(int i=0;i<=w;i++) { if(i==w-v[1]) { dp[1][i]=1; } } if(n==1){ if(v[1]<=w){ System.out.println(2); }else{ System.out.println(1); } return ; }else{ for(int i=2;i<=n;i++) { for(int k=0;k<=w;k++) { dp[i][k]=dp[i-1][k]+(k+v[i]<=w?dp[i-1][v[i]+k]:0); //我估计就是这个v[i]+k 导致越界了 } } // for(int i=1;i<=n;i++) { // for(int k=0;k<=w;k++) { // System.out.print(dp[i][k]+" "); // } // System.out.println(); // } for(int i=0;i<=w;i++) { res+=dp[n][i]; } System.out.println(res); } } }
// 枚举前n/2个物品的组合,按体积排好序// 枚举后n/2个物品的组合,在排好序的组合里面二分查找// 总复杂度O(n/2*2^(n/2))#include <bits/stdc++.h> using namespace std; int v[35]; int main() { int n, w; scanf("%d%d", &n, &w); for (int i = 0; i < n; i++) scanf("%d", v + i); int ans = 0; int lcnt = n / 2, rcnt = n - n / 2; vector<long long> sorted; for (int s = 0; s < (1 << lcnt); s++) { long long cur = 0; for (int i = 0; i < lcnt; i++) if (s >> i & 1) cur += v[i]; sorted.push_back(cur); } sort(sorted.begin(), sorted.end()); for (int s = 0; s < (1 << rcnt); s++) { long long cur = 0; for (int i = 0; i < rcnt; i++) if (s >> i & 1) cur += v[lcnt + i]; cout << cur << endl; ans += upper_bound(sorted.begin(), sorted.end(), w - cur) - sorted.begin(); } printf("%d", ans); return 0; }