)
称砝码
华为OD机试 - 华为OD上机考试 100分题型
华为OD机试真题目录点击查看: 华为OD机试真题题库目录｜机考题库 + 算法考点详解
题目描述
现有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
输出描述
利用给定的砝码可以称出的不同的重量数
用例1
输入
2 1 2 2 1输出
5说明
可以表示出0，1，2，3，4五种重量。
题解一
思路：很容易想到newWeight = oldWeight + weight[i]，每次循环时只需要用已有的重量再加上新的砝码重量值即可。使用set集合去重，每次用放置新砝码时用集合中已有重量 + weight[i]即可，得到的结果继续放入集合中，待下次放置时使用。最终集合的大小便是结果。
c++
#include<iostream> #include<vector> #include<string> #include <utility> #include <sstream> #include<algorithm> #include<list> #include<queue> #include<set> using namespace std; int main() { int n; cin >> n; vector<int> weight(n); vector<int> nums(n); for (int i = 0; i < n; i++) { cin >>weight[i]; } for (int i = 0; i < n; i++) { cin >>nums[i]; } // 去重 set<int> s; s.insert(0); for (int i = 0; i < n; i++) { for (int j = 0; j < nums[i]; j++) { set<int>s1(s.begin(), s.end()); // 枚举 for (int x : s1) { s.insert(x + weight[i]); } } } cout << s.size(); return 0; }JAVA
import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] weight = new int[n]; int[] nums = new int[n]; for (int i = 0; i < n; i++) { weight[i] = scanner.nextInt(); } for (int i = 0; i < n; i++) { nums[i] = scanner.nextInt(); } scanner.close(); // 用 HashSet 进行去重 Set<Integer> s = new HashSet<>(); s.add(0); for (int i = 0; i < n; i++) { for (int j = 0; j < nums[i]; j++) { List<Integer> tempList = new ArrayList<>(s); List<Integer> newElements = new ArrayList<>(); for (int x : tempList) { newElements.add(x + weight[i]); } s.addAll(newElements); } } System.out.println(s.size()); } }Python
importsys# 读取输入n=int(sys.stdin.readline().strip())weight=list(map(int,sys.stdin.readline().split()))nums=list(map(int,sys.stdin.readline().split()))# 使用 set 进行去重s={0}foriinrange(n):for_inrange(nums[i]):temp_list=list(s)new_elements=[x+weight[i]forxintemp_list]s.update(new_elements)print(len(s))JavaScript
constreadline=require("readline");constrl=readline.createInterface({input:process.stdin,output:process.stdout});letinput=[];rl.on("line",(line)=>{input.push(line.trim());if(input.length===3){letn=parseInt(input[0]);letweight=input[1].split(" ").map(Number);letnums=input[2].split(" ").map(Number);// 使用 Set 进行去重lets=newSet();s.add(0);for(leti=0;i<n;i++){for(letj=0;j<nums[i];j++){lettempList=Array.from(s);letnewElements=tempList.map(x=>x+weight[i]);newElements.forEach(e=>s.add(e));}}console.log(s.size);rl.close();}});Go
packagemainimport("bufio""fmt""os""strconv""strings")funcmain(){// 读取输入reader:=bufio.NewReader(os.Stdin)nStr,_:=reader.ReadString('\n')n,_:=strconv.Atoi(strings.TrimSpace(nStr))weightStr,_:=reader.ReadString('\n')weight:=strToIntArray(weightStr)numsStr,_:=reader.ReadString('\n')nums:=strToIntArray(numsStr)// 使用 map 作为 set 进行去重s:=make(map[int]bool)s[0]=truefori:=0;i<n;i++{forj:=0;j<nums[i];j++{tempList:=make([]int,0,len(s))forkey:=ranges{tempList=append(tempList,key)}newElements:=make([]int,len(tempList))fork,x:=rangetempList{newElements[k]=x+weight[i]}for_,newVal:=rangenewElements{s[newVal]=true}}}fmt.Println(len(s))}// strToIntArray 将输入字符串转换为整数数组funcstrToIntArray(inputstring)[]int{fields:=strings.Fields(input)arr:=make([]int,len(fields))fori,v:=rangefields{arr[i],_=strconv.Atoi(v)}returnarr}题解二
思路：完全背包算法处理,dp[j] = dp[j - weight[i] * num]
c++
#include<iostream> #include<vector> #include<string> #include <utility> #include <sstream> #include<algorithm> #include<list> #include<queue> #include<set> using namespace std; int main() { int n; cin >> n; vector<int> weight(n); vector<int> nums(n); for (int i = 0; i < n; i++) { cin >>weight[i]; } for (int i = 0; i < n; i++) { cin >>nums[i]; } // 完全背包 int sum = 0; for (int i = 0; i < n; i++) { sum += weight[i] * nums[i]; } vector<int> dp(sum + 1, 0); dp[0] = 1; // 完全背包 for (int i = 0; i < n; i++) { for (int j = 1; j <= nums[i]; j++) { for (int k = sum; k >= weight[i] * j; k--) { if (dp[k - weight[i]]) { dp[k] = 1; } } } } int count = 0; for (int i = 0; i <= sum; i++) { if (dp[i]) { count++; } } cout << count; return 0; }JAVA
import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] weight = new int[n]; int[] nums = new int[n]; for (int i = 0; i < n; i++) { weight[i] = scanner.nextInt(); } for (int i = 0; i < n; i++) { nums[i] = scanner.nextInt(); } scanner.close(); // 计算总重量 int sum = 0; for (int i = 0; i < n; i++) { sum += weight[i] * nums[i]; } // 完全背包 DP boolean[] dp = new boolean[sum + 1]; dp[0] = true; // 初始状态 for (int i = 0; i < n; i++) { for (int j = 1; j <= nums[i]; j++) { for (int k = sum; k >= weight[i] * j; k--) { if (dp[k - weight[i]]) { dp[k] = true; } } } } // 统计可达的重量数 int count = 0; for (boolean v : dp) { if (v) count++; } System.out.println(count); } }Python
importsys# 读取输入n=int(sys.stdin.readline().strip())weight=list(map(int,sys.stdin.readline().split()))nums=list(map(int,sys.stdin.readline().split()))# 计算总重量sum_weight=sum(weight[i]*nums[i]foriinrange(n))# 完全背包 DPdp=[0]*(sum_weight+1)dp[0]=1# 初始状态foriinrange(n):forjinrange(1,nums[i]+1):forkinrange(sum_weight,weight[i]*j-1,-1):ifdp[k-weight[i]]:dp[k]=1# 统计可达的重量数print(sum(dp))JavaScript
constreadline=require("readline");constrl=readline.createInterface({input:process.stdin,output:process.stdout});letinput=[];rl.on("line",(line)=>{input.push(line.trim());if(input.length===3){letn=parseInt(input[0]);letweight=input[1].split(" ").map(Number);letnums=input[2].split(" ").map(Number);// 计算总重量letsum=0;for(leti=0;i<n;i++){sum+=weight[i]*nums[i];}// 完全背包 DPletdp=newArray(sum+1).fill(0);dp[0]=1;for(leti=0;i<n;i++){for(letj=1;j<=nums[i];j++){for(letk=sum;k>=weight[i]*j;k--){if(dp[k-weight[i]]){dp[k]=1;}}}}// 统计可达的重量数letcount=dp.reduce((acc,val)=>acc+val,0);console.log(count);rl.close();}});Go
packagemainimport("bufio""fmt""os""strconv""strings")funcmain(){// 读取输入reader:=bufio.NewReader(os.Stdin)nStr,_:=reader.ReadString('\n')n,_:=strconv.Atoi(strings.TrimSpace(nStr))weightStr,_:=reader.ReadString('\n')weight:=strToIntArray(weightStr)numsStr,_:=reader.ReadString('\n')nums:=strToIntArray(numsStr)// 计算总重量sum:=0fori:=0;i<n;i++{sum+=weight[i]*nums[i]}// 完全背包 DPdp:=make([]bool,sum+1)dp[0]=true// 初始状态fori:=0;i<n;i++{forj:=1;j<=nums[i];j++{fork:=sum;k>=weight[i]*j;k--{ifdp[k-weight[i]]{dp[k]=true}}}}// 统计可达的重量数count:=0for_,v:=rangedp{ifv{count++}}fmt.Println(count)}// strToIntArray 将输入字符串转换为整数数组funcstrToIntArray(inputstring)[]int{fields:=strings.Fields(input)arr:=make([]int,len(fields))fori,v:=rangefields{arr[i],_=strconv.Atoi(v)}returnarr}
