鲁康华


私信TA

用户名:uq_32497986585

访问量:1225

签 名:

我菠萝吹雪浪迹一生 最幸福的时候就是梨花诗说愿意的...

等  级
排  名 2749
经  验 2119
参赛次数 1
文章发表 10
年  龄 0
在职情况 学生
学  校 鄂州职业大学
专  业

  自我简介:

我菠萝吹雪 行走江湖多年 原本打算封心锁爱 没想到看到你还是会心动 我的梨花诗

解题思路:

注意事项:    

将砝码独立来看,

在当前砝码称出重量x的情况下,对于砝码i都有三种操作:


x+砝码i的重量(放同侧)

x-砝码i的重量(放异侧)

x(不放)

显然前面两种操作才有可能产生不同的重量。

另外砝码i一定能称出其自身的重量


又考虑到set能够用于排除相等的元素

由于砝码称出的重量是正的,因此将操作获得的结果取绝对值再放入集合中


1.jpg2.jpg

以上的图解只分析了两种情况 ,所有需要画出所有的情况,就会画出一颗树。

左子树代表选择放入新的砝码,右子树表示不放入新的砝码,也就是继承上次的重量。

注意:左子树可能会秤出两种重量

3.jpg参考代码:

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        Set<Integer> set = new HashSet<>();
        int n = scan.nextInt();
        int[] fama = new int[n];
        for (int i = 0; i < n; i++) {
            fama[i] = scan.nextInt();
        }
        //初始化set,表示一开始天平上没有砝码,重量为0
        set.add(0);
        for (int i = 0; i < n; i++) {
            //在没放入新的砝码前,将秤得的所有重量放入list集合中
            List<Integer> list = new ArrayList<>(set);
            for (int k : list) {
                //相加和相减取绝对值产生新的两个重量,并加重量放入set集合中
                //注意:如果新秤得的重量在原来的set集合存在,将不被放入set中
                set.add(k + fama[i]);
                set.add(Math.abs(k - fama[i]));
            }
        }
        //移除0元素
        set.remove((Object)0);
        //输出set集合大小,即秤得的重量数
        System.out.println(set.size());
    }
}

DP版本思路差不多

import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		//存放砝码重量
		int a[] = new int[n];
		int sum = 0;
		for(int i = 0; i < n; i++){
			a[i] = sc.nextInt();
			sum += a[i];
		}
		
		int cnt = 0;
		boolean dp[][] = new boolean[n][sum+1];
	
		dp[0][a[0]] = true;
		
		for(int i = 1; i < n; i++){
			//将上一个状态复制过来
			for(int j = 1; j <= sum; j++)
				dp[i][j] = dp[i-1][j];
				
			dp[i][a[i]] = true;
			
			for(int j = 1; j <= sum; j++){
				if(dp[i-1][j]){
					dp[i][j+a[i]] = true;
					dp[i][Math.abs(j-a[i])] = true;
				}
			}
		}
		for(int i = 1; i <= sum; i++)
			if(dp[n-1][i])
				cnt++;
		System.out.println(cnt);
	}
}


 

0.0分

2 人评分

  评论区

两个办法都不错,比其他人的好理解一些!
2024-04-07 20:42:08
  • «
  • 1
  • »