牛牛的背包问题

[编程题]牛牛的背包问题

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

牛牛准备参加学校组织的春游, 出发前牛牛准备往背包里装入一些零食, 牛牛的背包容量为w。

牛牛家里一共有n袋零食, 第i袋零食体积为v[i]。

牛牛想知道在总体积不超过背包容量的情况下,他一共有多少种零食放法(总体积为0也算一种放法)。

输入描述:

输入包括两行
第一行为两个正整数n和w(1 <= n <= 30, 1 <= w <= 2 * 10^9),表示零食的数量和背包的容量。
第二行n个正整数v[i](0 <= v[i] <= 10^9),表示每袋零食的体积。

输出描述:

输出一个正整数, 表示牛牛一共有多少种零食放法。

示例1

输入

3 10
1 2 4

输出

说明

三种零食总体积小于10,于是每种零食有放入和不放入两种情况，一共有2*2*2 = 8种情况。

算法知识视频讲解

JavaScript

小阿群

思路是分而治之，参考了左神实现，这里为了简化代码并没有手动实现有序表，可自行将map替换。

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);

发表于 2022-05-31 15:41:16 回复(0)