首先看一下题

描述

现有n种砝码，重量互不相等，分别为 m1,m2,m3…mn ；
每种砝码对应的数量为 x1,x2,x3...xn 。现在要用这些砝码去称物体的重量(放在同一侧)，问能称出多少种不同的重量。

注：

称重重量包括 0

数据范围：每组输入数据满足  1≤n≤10  ， 1≤mi​≤2000  ， 1≤xi​≤10 

输入描述：

对于每组测试数据：
第一行：n --- 砝码的种数(范围[1,10])
第二行：m1 m2 m3 ... mn --- 每种砝码的重量(范围[1,2000])
第三行：x1 x2 x3 .... xn --- 每种砝码对应的数量(范围[1,10])

输出描述：

利用给定的砝码可以称出的不同的重量数

示例1

输入：

2
1 2
2 1

输出：

5

说明：

可以表示出0，1，2，3，4五种重量。   

一、问题分析

首先读题，仔细看描述中的内容，发现需求是

1.现在有n种砝码

2.重量互不相等

3.分别为m1,m2,m3...mn;

4.每种砝码对应的数量为x1,x2,x3...xn。

5.现在要用这些砝码去称物体的重量（放在同一侧），

6.问能称出多少种不同的重量。

7.称重重量包括0

8.数据范围：每组输入数据满足n大于等于1小于等于10，mi大于等于1小于等于2000，xi大于等于1，小于等于10

9.输入描述：对于每组测试数据：

第一行：n 法码的种数（范围[1,10]）

第二行：m1 m2 m3 .. mn 每种砝码的重量（范围[1,2000]）

第三行：x1 x2 x3 ... xn 每种砝码对应的数量（范围[1,10]）

10.输出描述：利用给定的砝码可以称出的不同的重量数

二、解题思路

1.首先我们最大可以称量的重量是2000*10*10 = 200000

2.我们可以定义一个int dp[200001] = {0};用来标记我们是否已经称量过某个重量

3.我们定义一个int count = 0；用来计算我们可以称量的不同的重量数

4.我们定义一个int n 用来存储砝码的种数

5.我们定义一个int m[n]用来存放每种砝码的重量

6.我们定义一个int x[n];用来存放每种砝码对应的数量

7.之后我们希望计算不同砝码的组合能够组成的重量值

8.计算出来重量值如果dp[重量] == 0;那么我们count++，dp[重量] = 1;

如果已经计算过了，我们不重复计算

三、具体步骤

使用的语言是C

#include <stdio.h>int main() {int n;while(scanf("%d", &n) != EOF) {int m[n];for(int i = 0; i < n; i++) {scanf("%d", &m[i]);}int x[n];for(int i = 0; i < n; i++) {scanf("%d", &x[i]);}// total用来计算我们可以称量的最大重量int total = 0;for(int i = 0; i < n; i++) {// 使用每种砝码的重量乘以数量得到每种砝码最大承重量，再相加total += m[i] * x[i];}// 定义一个数组可以表示某个重量是否称量过，第一个元素为1（代表称量过）int arr[200001] = {1};for(int i = 0; i < n; i++) {// 循环遍历每种砝码for(int j = 0; j < x[i]; j++) {// 遍历当前砝码(第i个)的个数x[i]for(int k = total; k >= 0; k--) {// 遍历所有的重量if(arr[k]) {// 如果遇到称量过的重量（以0为开始），我们将当前的这个砝码的重量也加上去，标记为称量过了arr[k + m[i]] = 1;}}}}int count = 0;for (int i = 0; i <= total; i++) {if(arr[i] == 1) {count++;}}printf("%d\n", count);return 0;}
}