题目描述
现有n种砝码，重量互不相等，分别为 m1,m2,m3…mn ；
每种砝码对应的数量为 x1,x2,x3…xn 。现在要用这些砝码去称物体的重量(放在同一侧)，问能称出多少种不同的重量。
输入描述
对于每组测试数据：
第一行：n — 砝码的种数(范围[1,10])
第二行：m1 m2 m3 … mn — 每种砝码的重量(范围[1,2000])
第三行：x1 x2 x3 …. xn — 每种砝码对应的数量(范围[1,10])
输出描述
利用给定的砝码可以称出的不同的重量数
备注
数据范围：每组输入数据满足：
- 1 ≤ n ≤ 10
- 1 ≤ mi ≤ 2000
- 1 ≤ xi ≤ 10
用例
| 输入 | 2 1 2 2 1 |
| 输出 | 5 |
| 说明 | 可以表示出0，1，2，3，4五种重量。 |
题目解析
本题可以使用多重背包求解。关于多重背包问题，其实就是01背包的变种问题。
01背包问题：
有N种物品，每种物品只有一个，第 i 个物品的重量为 wi，价值为pi，另外还有一个承重为W的背包，问该背包在不超载的情况下，装入物品的最大价值是多少?
多重背包问题
有N种物品，第 i 个物品的重量为 wi，价值为pi，数量为ci，另外还有一个承重为W的背包，问该背包在不超载的情况下，装入物品的最大价值是多少?
想求解多重背包问题，需要先弄得01背包问题，最好也了解下01背包的滚动数组优化：
算法设计 – 01背包问题的状态转移方程优化，以及完全背包问题_01背包问题状态转移方程_伏城之外的博客-CSDN博客
学会01背包后，多重背包问题的求解就非常简单了，其实我们可以将多重背包问题，转化为01背包问题，怎么转化呢？
举个例子：你有红富士苹果10个，那么是不是等价于红富士苹果A有1个，红富士苹果B有1个，…，红富士苹果J有1个？
其实这就是多重背包转化为01背包的方法。即将1种物品N个，转化为N种物品1个。
关于多重背包的求解有两种解法：
1、朴素解法
2、二进制优化解法
这两种解法具体逻辑请看：华为校招机试 – 攻城战（Java & JS & Python）_伏城之外的博客-CSDN博客
本题中
- N种砝码 → N种物品
- 每种砝码的重量 → 每种物品的重量
- 每种砝码的重量 → 每种物品的价值
- 每种砝码的数量 → 每种物品的数量
- 所有砝码的重量之和 → 背包承重
本题要求的是：用给的砝码能组合出多少种重量
而这其实刚好和求解背包问题时，遍历所有可能的背包承重相符，因此本题非常适合当成背包问题求解。
朴素解法
JavaScript算法源码
/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
const lines = [];
rl.on("line", (line) => {
lines.push(line);
if (lines.length === 3) {
const n = Number(lines[0]);
const m = lines[1].split(" ").map(Number);
const x = lines[2].split(" ").map(Number);
console.log(getResult(n, m, x));
lines.length = 0;
}
});
/**
* @param {*} n 砝码的种数
* @param {*} m 每种砝码的重量
* @param {*} x 每种砝码对应的数量
*/
function getResult(n, m, x) {
m = [0, ...m];
x = [0, ...x];
let bag = 0;
for (let i = 1; i <= n; i++) bag += m[i] * x[i];
const dp = new Array(bag + 1).fill(false);
dp[0] = true;
for (let i = 1; i <= n; i++) {
for (let j = bag; j >= m[i]; j--) {
for (let k = 1; k <= x[i]; k++) {
if (j >= m[i] * k) {
if (dp[j - m[i] * k]) dp[j] = true;
}
}
}
}
return dp.filter((f) => f).length;
}
Java算法源码
import java.util.Scanner;
import java.util.HashSet;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] m = new int[n + 1];
for (int i = 1; i <= n; i++) {
m[i] = sc.nextInt();
}
int[] x = new int[n + 1];
for (int i = 1; i <= n; i++) {
x[i] = sc.nextInt();
}
System.out.println(getResult(n, m, x));
}
public static int getResult(int n, int[] m, int[] x) {
int bag = 0;
for (int i = 1; i <= n; i++) bag += m[i] * x[i];
boolean[] dp = new boolean[bag + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = bag; j >= m[i]; j--) {
for (int k = 1; k <= x[i]; k++) {
if (j >= m[i] * k) {
if (dp[j - m[i] * k]) dp[j] = true;
}
}
}
}
int count = 0;
for (boolean flag : dp) {
if (flag) count++;
}
return count;
}
}Python算法源码
Python朴素解法实测超时，请使用二进制优化解法
# 输入获取
n = int(input())
m = list(map(int, input().split()))
x = list(map(int, input().split()))
# 算法入口
def getResult(n, m, x):
m.insert(0, 0)
x.insert(0, 0)
bag = 0
for i in range(1, n + 1):
bag += m[i] * x[i]
dp = [False] * (bag + 1)
dp[0] = True
for i in range(1, n + 1):
for j in range(bag, m[i] - 1, -1):
for k in range(1, x[i] + 1):
if j >= m[i] * k:
if dp[j - m[i] * k]:
dp[j] = True
return len(list(filter(lambda x: x, dp)))
# 算法调用
print(getResult(n, m, x))
二进制优化解法
JavaScript算法源码
/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
const lines = [];
rl.on("line", (line) => {
lines.push(line);
if (lines.length === 3) {
const n = Number(lines[0]);
const m = lines[1].split(" ").map(Number);
const x = lines[2].split(" ").map(Number);
console.log(getResult(n, m, x));
lines.length = 0;
}
});
/**
* @param {*} n 砝码的种数
* @param {*} m 每种砝码的重量
* @param {*} x 每种砝码对应的数量
*/
function getResult(n, m, x) {
let bag = 0;
const newM = [];
for (let i = 0; i < n; i++) {
// 背包承重等于所有砝码重量之和
bag += m[i] * x[i];
// 将1种物品N个，进行二进制优化
for (let j = 1; j <= x[i]; j <<= 1) {
newM.push(m[i] * j);
x[i] -= j;
}
if (x[i] != 0) {
newM.push(x[i] * m[i]);
}
}
// 01背包滚动数组优化求解
const dp = new Array(bag + 1).fill(false);
// 0重量组合肯定存在
dp[0] = true;
for (let w of newM) {
for (let j = bag; j >= w; j--) {
// 如果j-w组合重量存在，那么j重量组合也一定存在
if (dp[j - w]) dp[j] = true;
}
}
return dp.filter((f) => f).length;
}
Java算法源码
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] m = new int[n + 1];
for (int i = 1; i <= n; i++) {
m[i] = sc.nextInt();
}
int[] x = new int[n + 1];
for (int i = 1; i <= n; i++) {
x[i] = sc.nextInt();
}
System.out.println(getResult(n, m, x));
}
public static int getResult(int n, int[] m, int[] x) {
int bag = 0;
ArrayList<Integer> newM = new ArrayList<>();
for (int i = 1; i <= n; i++) {
// 背包承重等于所有砝码重量之和
bag += m[i] * x[i];
// 将1种物品N个，进行二进制优化
for (int j = 1; j <= x[i]; j <<= 1) {
newM.add(m[i] * j);
x[i] -= j;
}
if (x[i] != 0) {
newM.add(m[i] * x[i]);
}
}
// 01背包滚动数组优化求解
boolean[] dp = new boolean[bag + 1];
// 0重量组合肯定存在
dp[0] = true;
for (Integer w : newM) {
for (int j = bag; j >= w; j--) {
// 如果j-w组合重量存在，那么j重量组合也一定存在
if (dp[j - w]) dp[j] = true;
}
}
int count = 0;
for (boolean flag : dp) {
if (flag) count++;
}
return count;
}
}
Python算法源码
# 输入获取
n = int(input())
m = list(map(int, input().split()))
x = list(map(int, input().split()))
# 算法入口
def getResult(n, m, x):
bag = 0
newM = []
for i in range(n):
# 背包承重等于所有砝码重量之和
bag += m[i] * x[i]
# 将1种物品N个，进行二进制优化
j = 1
while j <= x[i]:
newM.append(m[i] * j)
x[i] -= j
j <<= 1
if x[i] != 0:
newM.append(m[i] * x[i])
# 01背包滚动数组优化求解
dp = [False] * (bag + 1)
# 0重量组合肯定存在
dp[0] = True
for w in newM:
for j in range(bag, w - 1, -1):
# 如果j-w组合重量存在，那么j重量组合也一定存在
if dp[j - w]:
dp[j] = True
return len(list(filter(lambda x: x, dp)))
# 算法调用
print(getResult(n, m, x))
免责声明：
1、IT资源小站为非营利性网站，全站所有资料仅供网友个人学习使用，禁止商用
2、本站所有文档、视频、书籍等资料均由网友分享，本站只负责收集不承担任何技术及版权问题
3、如本帖侵犯到任何版权问题，请立即告知本站，本站将及时予与删除下载链接并致以最深的歉意
4、本帖部分内容转载自其它媒体，但并不代表本站赞同其观点和对其真实性负责
5、一经注册为本站会员，一律视为同意网站规定，本站管理员及版主有权禁止违规用户
6、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者和IT资源小站的同意
7、IT资源小站管理员和版主有权不事先通知发贴者而删除本文
评论0