现有n种砝码，重量互不相等，分别为 m1,m2,m3…mn ；
每种砝码对应的数量为 x1,x2,x3...xn 。现在要用这些砝码去称物体的重量(放在同一侧)，问能称出多少种不同的重量。
注：
称重重量包括 0
数据范围：每组输入数据满足 
， 
， 
[编程题]称砝码
- 热度指数：200519 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
对于每组测试数据： 第一行：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五种重量。
#include <iostream>
#include <vector>
using namespace std;
int main(){
int n;
while(cin>>n)
{
int w[10],num[10];
for(int i=0;i<n;i++)
cin>>w[i];
for(int i=0;i<n;i++)
cin>>num[i];
/*数据处理：
1.将第0种砝码（m1）能称出的重量在标记数组中记录；
2.定义已经知道能称出的不同重量数的一堆砝码为基础堆，基础堆外的其余砝码组成剩余堆。显然第一个基础堆为x1个m1砝码组成的一堆砝码。
每次从剩余堆中拿出一个砝码放入到基础堆中，将由此新增的称重重量在标记数组中标记，新增的称重重量为基础堆能称出的所有称重重量各加上
一个新添砝码重量，标记数组下标的唯一性保证重复出现的称重重量最后只被统计一次；
3.待剩余堆为空后，统计标记数组中的非0元素的个数，即为所有砝码能称出的不同重量数
*/
int allwmax=0; //定义所给砝码能称出的最大重量并初始化
for(int i=0;i<n;i++)
allwmax+=w[i]*num[i];
vector<int> flag(allwmax+1,0);//给出标记数组的尺寸，并初始化为全0
for(int i=0;i<=num[0];i++)
flag[w[0]*i]=1;
int nowwmax=w[0]*num[0]; //定义当前最大称重重量并初始化
for(int i=1;i<n;i++) //往x1个m1砝码（第0种砝码）依次加入剩余所有砝码，一种加完再加另一种，具体顺序为w[1]~w[n-1]
{
for(int j=1;j<=num[i];j++)
{
for(int k=nowwmax;k>=0;k--) //为了防止新增重量不出现在当前基础堆的称重重量中导致加两次，需要倒序遍历当前基础堆的称重重量
if(flag[k]) //k每次减1，故k不一定是当前基础堆的称重重量，只有flag[k]=1的k才是
flag[k+w[i]]=1;
nowwmax+=w[i]; //当前基础堆所有称重重量都加上新添砝码重量后，当前最大称重重量自增新添砝码重量
}
}
/*剩余堆为空后统计标记数组中的非0元素的个数，即为所有砝码能称出的不同重量数*/
int sum=0;
for(int i=0;i<flag.size();i++)
if(flag[i]) sum++;
cout<<sum<<endl;
}
return 0;
}
发表于 2018-07-02 18:31:41
回复(0)
import java.util.Scanner;
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
static Deque<Integer> path = new LinkedList<>();
static Set<Integer> set = new HashSet<>();
static ArrayList<ArrayList<Integer>> result = new ArrayList<>();
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
int kind = in.nextInt();
int[] kinds = new int[kind];
int[] num=new int[kind];
for(int i=0;i<kind;i++){
kinds[i]=in.nextInt();
}
int sum=0;
for(int i=0;i<kind;i++){
num[i]=in.nextInt();
sum+=num[i];
}
int[] arr = new int[sum];
int count=0;
for(int j=0;j<kind;j++){
int numOfCur=num[j];
while(numOfCur!=0){
arr[count]=kinds[j];
count++;
numOfCur--;
}
}
Arrays.sort(arr);
backTracking(arr,0);
// System.out.println(Arrays.toString(arr));
int rrr=0;
for(ArrayList<Integer> list: result){
int curSum=0;
for(Integer snum: list){
curSum+=snum;
// System.out.print(snum);
}
if(!set.contains(curSum)){
rrr++;
set.add(curSum);
}
// System.out.println();
}
System.out.println(rrr);
}
public static void backTracking(int[] arr,int index){
result.add(new ArrayList<>(path));
for(int i=index;i<arr.length;i++){
if ( i > index && arr[i - 1] == arr[i] ) {
continue;
}
path.addLast(arr[i]);
backTracking(arr,i+1);
path.removeLast();
}
}
} 想法是将所有砝码放到一个数组里面，然后将数组进行组合，组合相加后去重从而获得总次数，但是会超时！！！！写了很久不想浪费，做一个纪念。
发表于 2022-03-30 10:54:16
回复(1)
坑点：0也要加进set里面
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner in = new Scanner(System.in);
while(in.hasNextInt()){
int n = in.nextInt();
int m[] = new int [n];
int x[] = new int [n];
for(int i = 0; i < n; i++)
m[i] = in.nextInt();
for(int i = 0; i < n; i++)
x[i] = in.nextInt();
category(n, m, x);
}
in.close();
}
public static void category(int n, int m[], int x[]){
HashSet<Integer> set = new HashSet<Integer>();
set.add(0);
for(int i = 0; i < n; i++){
List<Integer> list = new ArrayList<Integer>(set);
for(int j = 0; j <= x[i]; j++){
for(int k = 0; k < list.size(); k++){
set.add(list.get(k) + j * m[i]);
}
}
}
System.out.println(set.size());
}
}
发表于 2021-03-17 14:38:35
回复(0)
java hashset转数组对每个元素加砝码重量
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String n1 = null;
while ((n1 = bf.readLine()) != null) {
int n = Integer.parseInt(n1);
String[] s1 = bf.readLine().split(" ");
String[] s2 = bf.readLine().split(" ");
int[] weight = new int[s1.length];
int[] nums = new int[s2.length];
for (int i = 0; i < n; i++) {
weight[i] = Integer.parseInt(s1[i]);
nums[i] = Integer.parseInt(s2[i]);
}
System.out.println(fama(n, weight, nums));
}
}
public static int fama(int n, int[] weight, int[] nums) {
HashSet<Integer> set = new HashSet<>();
set.add(0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < nums[i]; j++) {
Object[] d = set.toArray();
for (int k = 0; k < d.length; k++) {
set.add((Integer) d[k] + weight[i]); //set中的已有元素再加上当前砝码重量
}
}
}
return set.size();
}
}
发表于 2020-09-26 11:36:20
回复(0)
#include "string.h"
#include <stdio.h>
#include "stdlib.h"
//期初放第一个砝码，就在该重量标志位置1，继续放砝码之前判断重量标志位哪些为1
//然后放上砝码，把相应标志位置1.
int main (void)
{
int num;
while (scanf("%d",&num)!=EOF)
{
int table[2][10]={0};
int i,j,k,q=0;
for (i=0;i<2;i++)
for (j=0;j<num;j++)
scanf("%d",&table[i][j]); //构建二维数组，第一行是不同砝码规格的重量，第二行是数量
int weight=0;
for (i=0;i<num;i++) weight=weight+table[0][i]*table[1][i]; //计算出最大重量
int p[10000]={0};
p[0]=1; //期初标志位
for (i=0;i<num;i++) //选取规格
{
for (j=0;j<table[1][i];j++) //该规格下的数量
{
for (k=weight;k>=0;k--) //遍历重量表，寻找重量标志位
{
if (p[k]==1) p[k+table[0][i]]=1; //刷新重量标志位
}
}
}
for (i=0;i<10000;i++)
{
if (p[i]==1) q++;
}
printf("%d\r\n",q);
}
}
发表于 2020-09-06 14:58:07
回复(0)
#include <iostream>
#include <vector>
#include <algorithm>
//需要读懂题 --
//按照砝码重量和数量，逐个推到vector中，且比较去重
using namespace std;
int main()
{
int n;
while(cin >> n)
{
int m[10]={0};
int x[10]={0};
for(int i = 0;i<n;i++)
cin>>m[i];
for(int i = 0;i<n;i++)
cin>>x[i];
vector<int> weight;
weight.push_back(0);//现将0放进数组，因为称重重量包括0
//开始进行逐个砝码进行比较和确认最终情况
for(int i = 0;i<n;i++)
{
int len = weight.size();
for(int j = 1;j<=x[i];j++)
{
int tmp = j*m[i];
if(i == 0) weight.push_back(tmp);
for(int z = 0;z<len;z++)
{
int res = weight[z] + tmp;
if(find(weight.begin(),weight.end(),res) == weight.end())//如果当前计算的重量数组里面没有，那么就放进去
weight.push_back(res);
}
}
}
cout<<weight.size()<<endl;
}
return 0;
}
发表于 2020-07-16 11:38:26
回复(1)
真羡慕你们用高级语言，，，参考第一个的思路693ms
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
typedef struct result_s
{
int sum;
struct result_s *next;
}SUM_S;
int main()
{
int total_num = 0;
int per_qlt[10] = {0};
int per_num[10] = {0};
SUM_S *psum_head = NULL;
SUM_S *psum_old_head = NULL;
SUM_S *psum_new = NULL;
SUM_S *psum_temp = NULL;
SUM_S *psum_temp2 = NULL;
int is_exist = 0;
int sum_size = 0;
int index_type = 0;
int use_per_type = 0;
int temp_sum = 0;
//scanf("%d", &total_num);
while(scanf("%d", &total_num) != EOF)
{
for(index_type = 0; index_type < total_num; index_type++)
{
scanf("%d", &per_qlt[index_type]);
}
for(index_type = 0; index_type < total_num; index_type++)
{
scanf("%d", &per_num[index_type]);
}
psum_head = (SUM_S *)malloc(sizeof(SUM_S));
memset(psum_head, 0, sizeof(SUM_S));
for(index_type = 0; index_type < total_num; index_type++)
{
psum_old_head = psum_head;
for(use_per_type = 1; use_per_type <= per_num[index_type]; use_per_type++)
{
psum_temp = psum_old_head;
while(psum_temp != NULL)
{
temp_sum = psum_temp->sum + (use_per_type * per_qlt[index_type]);
printf("(sum %d + use%dqlt%d) ", psum_temp->sum, use_per_type, per_qlt[index_type]);
psum_temp2 = psum_head;
while(psum_temp2 != NULL)
{
if(temp_sum == psum_temp2->sum)
{
is_exist = 1;
}
psum_temp2 = psum_temp2->next;
}
if(is_exist == 0)
{
psum_new = (SUM_S *)malloc(sizeof(SUM_S));
memset(psum_new, 0, sizeof(SUM_S));
psum_new->sum = temp_sum;
psum_new->next = psum_head;
psum_head = psum_new;
sum_size++;
printf("add %d\n", psum_new->sum);
}
is_exist = 0;
psum_temp = psum_temp->next;
}
}
}
printf("%d\n", sum_size + 1);
while(psum_head->next != NULL)
{
psum_temp = psum_head;
psum_head = psum_head->next;
free(psum_temp);
}
psum_head->sum = 0;
sum_size = 0;
}
return 0;
}
发表于 2019-08-11 23:26:05
回复(0)
int fama(int n, int *weight, int *nums)
{
vector<int> now;
set<int> noww;
set<int> tempset;
int temp = 0;
for (int i = 0; i <= nums[0]; i++)
{
noww.insert(i*weight[0]);
}
for (int i = 1; i < n; i++)
{
for (auto j : noww)
{
for (int k = 0; k <= nums[i]; k++)
{
tempset.insert(k*weight[i] + j);
}
}
noww = tempset;
tempset.clear();
}
for (auto i : noww)
{
temp++;
//cout << i << endl;
}
{
vector<int> now;
set<int> noww;
set<int> tempset;
int temp = 0;
for (int i = 0; i <= nums[0]; i++)
{
noww.insert(i*weight[0]);
}
for (int i = 1; i < n; i++)
{
for (auto j : noww)
{
for (int k = 0; k <= nums[i]; k++)
{
tempset.insert(k*weight[i] + j);
}
}
noww = tempset;
tempset.clear();
}
for (auto i : noww)
{
temp++;
//cout << i << endl;
}
发表于 2018-08-06 14:30:06
回复(0)
这个题的时间要求为1s,为什么我1250ms过了？？
刚开始用的纯dfs，存放结果的数组没有优化， 每次判断存在都要遍历整个数组，结果肯定超时了。
优化为：存放结果的数组采用插入的方法保持有序，所以查询是否存在就使用了二分法，结果1250ms就过了？？？
package com.special.spet;
import java.util.Scanner;
/**
*
* @author special
* @date 2017年10月18日 下午1:52:14
*/
public class Pro40 {
public static int n;
public static int[] weight = new int[10 + 5];
public static int[] number = new int[10 + 5];
public static int kinds;
public static int[] result;
private static boolean contains(int weight){
int low = 0;
int high = kinds - 1;
while(low <= high){
int mid = low + (high - low) / 2;
if(weight < result[mid]) high = mid - 1;
else if(weight > result[mid]) low = mid + 1;
else return true;
}
return false;
}
private static void insert(int weight){
int i = kinds - 1;
for(; i >= 0; i--){
if(weight < result[i])
result[i + 1] = result[i];
else
break;
}
result[i + 1] = weight;
kinds++;
}
public static void dfs(int index, int currentWeight){
if(index == n){
if(!contains(currentWeight))
insert(currentWeight);
return;
}
for(int i = 0; i <= number[index]; i++)
dfs(index + 1, currentWeight + i * weight[index]);
}
public static void main(String[] args){
Scanner input = new Scanner(System.in);
while(input.hasNext()){
n = input.nextInt();
result = new int[46656 + 5];
kinds = 0;
for(int i = 0; i < n; i++)
weight[i] = input.nextInt();
for(int i = 0; i < n; i++)
number[i] = input.nextInt();
dfs(0,0);
System.out.println(kinds);
}
}
}
发表于 2017-10-18 14:42:33
回复(1)
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <map>
#include <set>
#include <list>
#include <deque>
#include <algorithm>
#include <cctype>
#include <iomanip>
#include<cstdlib>
#include <functional>
#include <bitset>
using namespace std;
//称砝码
void fama()
{
int num;
while (cin >> num)
{
int num1 = num;
vector<int> weight;
vector<int> mount;
while (num1)
{
--num1;
int w;
cin >> w;
weight.push_back(w);
}
int sum = 0;
for (int i = 0; i < num;++i)
{
int m;
cin >> m;
sum += weight[i] * m;
mount.push_back(m);
}
vector<int> dp(sum + 1, 0);
dp[0] = 1;
for (int i = 0; i < num; ++i)
{
for (int j = 0; j < mount[i]; ++j)
{
for (int k = sum; k >= weight[i]; --k)
{
if (dp[k - weight[i]] == 1)
dp[k] = 1;
}
}
}
int result = 0;
for (auto elem : dp)
{
if (elem == 1)
++result;
}
cout << result << endl;
}
}
int main()
{
fama();
return 0;
}
发表于 2016-08-18 18:36:59
回复(1)
import java.util.Scanner;
import java.util.TreeSet;
public class Main{
public static void main(String[] args){
Scanner s=new Scanner(System.in);
while(s.hasNext()){
int n=s.nextInt();
int[] arr1=new int[n];
int[] arr2=new int[n];
int total=0;
for(int i=0;i<n;i++)
arr1[i]=s.nextInt();
for(int i=0;i<n;i++){
arr2[i]=s.nextInt();
total=total+arr1[i]*arr2[i];
}
TreeSet<Integer> set=new
TreeSet<Integer>();
set.add(total);
for(int i=0;i<n;i++){
Object[] set1=set.toArray();
for(Object a:set1){
int j=1;
while(j<=arr2[i]){
set.add((Integer)a-j*arr1[i]);
j++;
}
}
}
System.out.println(set.size());
}
}
}
发表于 2016-08-04 23:13:12
回复(1)
import java.util.ArrayList;import java.util.HashSet;import java.util.List;/***思路： 先将第一个砝码按个数不同放入set中；然后从1.....N-1依次判断当前第i个砝码放入时可称的重量种数* 即当第i个砝码放入时，将已放入set中的重量一一与j*weight[i]相加，并将未涉及的重量放入set。*/import java.util.Scanner;import java.util.Set;public class huiweiPro28 {public static void main(String[] args) {// TODO Auto-generated method stubScanner in = new Scanner(System.in);while (in.hasNext()) {int n = in.nextInt();int[] weight = new int[n];int[] nums = new int[n];for (int i = 0; i < n; i++) {weight[i] = in.nextInt();}for (int i = 0; i < n; i++) {nums[i] = in.nextInt();}System.out.println(fama(n, weight, nums));}in.close();}public static int fama(int n, int[] weight, int[] nums) {Set<Integer> set=new HashSet<Integer>();for(int i=0;i<=nums[0];i++){ //第一个砝码set.add(i*weight[0]);}for(int i=1;i<n;i++){//从第二个砝码依次判断List<Integer> list=new ArrayList<Integer>(set);for(int j=1;j<=nums[i];j++){//遍历该砝码的个数for(int k=0;k<list.size();k++){set.add(list.get(k)+j*weight[i]);}}}return set.size();}}
发表于 2016-05-29 11:05:36
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc= new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt();//输入数量
Integer[] ws = new Integer[n];
for(int i=0;i<n;i++){
ws[i] = sc.nextInt();
}
List<Integer> list = new ArrayList<Integer>();//所有砝码数
for(int i=0; i < n; i++){
int num = sc.nextInt();
for(int j = 0;j < num; j++){
list.add(ws[i]);
}
}
HashSet<Integer> set = new HashSet<>();//存放所有可能的结果
set.add(0);//初始一个0
for(int i = 0 ; i < list.size(); i++){//其实是进行排列组合,但是这里我们用结果进行存储计算
List<Integer> tmp = new ArrayList<Integer>(set);
for(int j = 0; j< tmp.size();j++){
set.add(tmp.get(j)+list.get(i));
}
}
System.out.println(set.size());
}
}
}
发表于 2022-02-25 17:14:40
回复(0)
该题就是回溯算法的子集问题。JAVA版本如下，但是会超时，这个还要怎么优化啊😅
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
/**
* @author m
* @Description 称砝码
* 思路：
* 1.求全排列的子集
* 2.对子集中所有元素，各自相加
* 3. 相同点元素和去重
* @creat 2021-07-20
*/
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String nn;
while((nn = bf.readLine())!= null){
int n = Integer.parseInt(nn);
String mm = bf.readLine();
String[] m = mm.trim().split(" ");
String xx = bf.readLine();
String[] x = xx.trim().split(" ");//每个砝码的数量
//子集来做：
int N=0;
for(int i=0; i<x.length;i++){
N += Integer.parseInt(x[i]);
}
String[] choice = new String[N];
int k=0;//choice的索引
//遍历x数组，将对应的砝码添加到choice中
for(int i=0;i<x.length;i++){
int num = Integer.parseInt(x[i]);
for(int j=0;j<num;j++){
choice[k++] = m[i];
}
}
//输出：
Set res= new HashSet();
int sum=0;
recur(choice,0,sum,res);
System.out.println(res.size());
}
}
static void recur(String[] choice, int start,int sum, Set res){
res.add(sum);
for(int i=start;i<choice.length;i++){
//做选择：
sum += Integer.parseInt(choice[i]);
//递归回溯：
recur(choice,i+1,sum,res);
//撤销选择
sum -= Integer.parseInt(choice[i]);
}
}
}
发表于 2021-07-21 14:00:32
回复(0)
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
using namespace std;
int main()
{ int n; while(cin>>n) { int a[n],b[n]; set<int> s={0},t={0}; for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<n;i++) cin>>b[i]; for(int i=0;i<n;i++) { for(int k=1;k<=b[i];k++) for(auto it:t) s.insert(it + k*a[i]); t = s; } cout<<s.size()<<endl; } return 0;
}
发表于 2018-06-03 01:28:13
回复(0)
//以第一个砝码为基础，在其基础上不断添加，如示例：
//砝码1的数量位2，则三种情况：0，1，2
//砝码2的数量位1，则两种情况：0，2
//在砝码3种的基础上，添加砝码2的两种情况，分别为：0，1，2；2，3，4；去掉重复情况，则为0，1，2，3，4
//依次类推，得出n种砝码的情况 import java.util.*;
public class Main{
public static int fama(int n, int[] weight, int[] nums){
Set<Integer> set = new HashSet<Integer>();
for(int i = 0; i <= nums[0]; i++){
set.add(weight[0] * i);
}
for(int i = 1; i < n; i++){
List<Integer> list = new ArrayList<Integer>(set);
for(int j = 0; j <= nums[i]; j++){
for(int k = 0; k < list.size(); k++){
set.add(list.get(k) + j * weight[i]);
}
}
}
return set.size();
}
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNext()){
int n = in.nextInt();
int[] weight = new int[n];
int[] nums = new int[n];
for(int i = 0; i < n; i++){
weight[i] = in.nextInt();
}
for(int i = 0; i < n; i++){
nums[i] = in.nextInt();
}
System.out.println(fama(n, weight, nums));
}
in.close();
}
}
发表于 2017-03-18 16:34:22
回复(9)
while True: try: a = int(input()) weight = list(map(int,input().split())) count = list(map(int,input().split())) fm,temp,ans = [],[],[0] # 将所有砝码放入列表 for i in range(a): for j in range(count[i]): fm.append(weight[i]) # 称重 for i in fm: temp = set(ans) for j in temp: ans.append(j+i) # 去重 print(len(set(ans))) except: break
编辑于 2020-03-04 17:41:41
回复(12)
/*思路：输入砝码种类n; 输入砝码质量w[i]; 输入砝码个数c[i]； 输出 可以拼凑的质量个数 w1 w2 w3 w4 ...... wn c1 c2 c3 c4 ...... cn 对于前i个砝码： （不同质量为Q[i])则 Q[i]=Q[i-1]+k*w[i]; -->0<=k<=c[i]; Q[i]在Q[i-1]的基础上，对Q[i-1]个不同的重量，分别添加k个砝码i; 在添加的过程中去除重复情况 c[i]表示N个不同砝码相应的数量 c[1~~n]; 则（结果）:Q[i]=(Q[i-1]+k*w[i])--(减去)添加过程中重复的个数 */
JAVA版参考：
import java.util.*; public class Main{ public static void main(String[] args){ Scanner cin=new Scanner(System.in); while(cin.hasNext()){ int n=cin.nextInt();//砝码种类 int[] weights=new int[n]; int[] numbers=new int[n]; for(int i=0;i<n;i++) weights[i]=cin.nextInt(); for(int i=0;i<n;i++) numbers[i]=cin.nextInt(); int result=function(n,weights,numbers); System.out.println(result); } cin.close(); } public static int function(int n,int[] weights,int[] numbers){ Set<Integer> set=new HashSet<Integer>(); for(int i=0;i<=numbers[0];i++) set.add(i*weights[0]); for(int i=1;i<n;i++){//从第二个砝码开始 List<Integer>list =new ArrayList<Integer>(set); for(int j=1;j<=numbers[i];j++){//遍历砝码的个数 for(int k=0;k<list.size();k++) set.add(list.get(k)+j*weights[i]); } } return set.size(); } }
C++版本参考
#include<iostream> #include<vector> #include<set> #include<algorithm> using namespace std; int main() { int n;//砝码数 int m[10]={0};//每个砝码的质量 int x[10]={0};//每个砝码的数量 while(cin>>n){ for(int i=0;i<n;i++) cin>>m[i]; for(int i=0;i<n;i++) cin>>x[i]; vector<int>weights; //存所有已经称出的砝码的质量。 /*先将第一个砝码称出的质量入队。*/ weights.push_back(0);//初始化weights数组 for(int i=1;i<=x[0];i++) weights.push_back(i*m[0]);//将第一个砝码能称出的质量入队 for(int i=1;i<n;i++){//前多少个砝码 //weights.push_back(m[i]); int len=weights.size();//记录已经称出砝码质量便于下面for循环 for(int j=1;j<=x[i];j++){//遍历该质量的砝码数 for(int k=0;k<len;k++){ int w=weights[k]+j*m[i];//将该质量的砝码数依次与前面所有的砝码数相加 //去重操作 if(find(weights.begin(),weights.end(),w)==weights.end())//如果之前没有这个质量的砝码就将其入队 weights.push_back(weights[k]+j*m[i]); } } } cout<<weights.size()<<endl; } }
编辑于 2016-07-22 15:19:55
回复(10)
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
int main()
{
/*从砝码1开始分析，假设前i个砝码能称出的不同重量为Q[i],那么Q[i]一定是这样计算出来的：在Q[i-1]的基础上，对Q[i-1]个不同的重量，分别添加k个砝码i，再添加的过程中除去重复情况。
//假设：w[N]表示N个不同重量的砝码（例子中N=6），w[0~N-1]。
// c[N]表示N个不同砝码相应的数量，c[1~N]。
//则：Q[i] = (Q[i-1] + k*w[i])-添加过程中重复的个数。其中0=<k<=c[i]。网上博客搜的解题思路*/
int n ;//砝码数
int m[10] = { 0 };//每个砝码的质量
int x[10] = { 0};//每个砝码的数量
while (cin >> n)
{
for (int i = 0; i < n; i++)
{
cin >> m[i];
}
for (int i = 0; i < n; i++)
{
cin >> x[i];
}
vector<int>weigths;//存所有已经称出的砝码的质量。
/*先将第一个砝码称出的质量入队。*/
weigths.push_back(0);//初始化weigths数组
for (int i = 1; i <= x[0]; i++)
{
weigths.push_back(i*m[0]);//将第一个砝码能称出的所有质量入队。
}
for (int i = 1; i < n; i++)//前多少个砝码
{
//weigths.push_back(m[i]);
int len = weigths.size();//记录已经称出的砝码质量便于下面for循环使用
for (int j = 1; j <= x[i]; j++)//遍历该质量的砝码数
{
for (int z = 0; z < len; z++)
{
int wei = weigths[z] + j*m[i];//将该质量的砝码数依次与前面所有的砝码数相加
if (find(weigths.begin(), weigths.end(), wei) == weigths.end())//如果之前没有这个质量的砝码就将其入队
weigths.push_back(weigths[z] + j*m[i]);
}
}
}
//set<int>wi(weigths.cbegin(), weigths.cend());//这一步是为了将weigths中的数字进一步去重保证正确性。
cout << weigths.size() << endl;
//cout << wi.size() << endl;
}
//system("pause");
return 0;
}
编辑于 2016-05-28 17:45:40
回复(22)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int n;
while(cin>>n){
vector<int> weight(n);
vector<int> num(n);
for(int i=0;i<n;i++)
cin>>weight[i];
for(int i=0;i<n;i++)
cin>>num[i];
vector<int> ans;
for(int i=0;i<=num[0];i++){
ans.push_back(i*weight[0]);
}
for(int j=1;j<n;j++){
int size=ans.size();
for(int i=1;i<=num[j];i++)
for(int m=0;m<size;m++){
if(find(ans.begin(),ans.end(),ans[m]+i*weight[j])==ans.end())
ans.push_back(ans[m]+i*weight[j]);
}
}
cout<<ans.size()<<endl;
}
return 0;
}
编辑于 2016-08-09 13:05:31
回复(4)
问题信息
难度：
349条回答
3953收藏
41960浏览
通过挑战的用户
查看代码-
2023-03-02 16:26:09
-
2023-01-10 22:56:28 -
2023-01-07 17:01:38 -
2022-10-28 15:21:35
-
2022-10-27 22:39:47
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
