問(wèn)題描述

你有一架天平和?N?個(gè)砝碼，這?N?個(gè)砝碼重量依次是?W_1, W_2, · · · , W_N。

請(qǐng)你計(jì)算一共可以稱出多少種不同的重量？ 注意砝碼可以放在天平兩邊。

輸入格式

輸入的第一行包含一個(gè)整數(shù) N。

第二行包含 N?個(gè)整數(shù)：W_1, W_2, W_3, · · · , W_N?。

輸出格式

輸出一個(gè)整數(shù)代表答案。

樣例輸入

3
1 4 6

樣例輸出

10

樣例說(shuō)明

能稱出的 10 種重量是：1、2、3、4、5、6、7、9、10、11

問(wèn)題分析：

首先分析問(wèn)題的類型，每一個(gè)砝碼只能選擇取或者不取，類似于01背包問(wèn)題。

每一種不同重量都可以從計(jì)算上次秤出的重量中上得出，這句話可能大家沒(méi)有太明白。

我這里解釋一下，比如說(shuō)：

假設(shè)砝碼a，b，c的重量分別為1，4，6

一開(kāi)始，天平上只有砝碼a，天平上只有砝碼a說(shuō)明秤出的重量只有1。

此時(shí)我們可以不放砝碼b，或者放砝碼b

放入砝碼b就會(huì)秤出重量5和3，即4+1=5和4-1=3，我們可以把5和3作為新的砝碼，等放入下一個(gè)砝碼時(shí)，就可以在原來(lái)秤出的重量上計(jì)算新的重量

不放入b，天平上還是原來(lái)的重量

算法圖解：

圖解一：分析先放入a，再放入b，在放入c的圖解

圖解二：分析不放入a，再放入b，再放入c的情況

以上的圖解只分析了兩種情況 ，所有需要畫(huà)出所有的情況，就會(huì)畫(huà)出一顆樹(shù)。

左子樹(shù)代表選擇放入新的砝碼，右子樹(shù)表示不放入新的砝碼，也就是繼承上次的重量。

注意：左子樹(shù)可能會(huì)秤出兩種重量

根據(jù)以上圖解我們可以得出，每次放入新的砝碼，都可以從上一次秤得的重量中計(jì)算得出。

完整代碼如下：

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,表示一開(kāi)始天平上沒(méi)有砝碼，重量為0
        set.add(0);
        for (int i = 0; i < n; i++) {
            //在沒(méi)放入新的砝碼前，將秤得的所有重量放入list集合中
            List<Integer> list = new ArrayList<>(set);
            for (int k : list) {
                //相加和相減取絕對(duì)值產(chǎn)生新的兩個(gè)重量，并加重量放入set集合中
                //注意:如果新秤得的重量在原來(lái)的set集合存在，將不被放入set中
                set.add(k + fama[i]);
                set.add(Math.abs(k - fama[i]));
            }
        }
        //移除0元素
        set.remove((Object)0);
        //輸出set集合大小，即秤得的重量數(shù)
        System.out.println(set.size());
    }
}

運(yùn)行結(jié)果：

?當(dāng)然了，本人也使用過(guò)遞歸爆搜的解法，由于利用暴力搜索的方法會(huì)產(chǎn)生大量的重復(fù)計(jì)算，

所以提交答案會(huì)提示超時(shí)，代碼給有需要的讀者作為參考：

import java.util.*;
// 1:無(wú)需package
// 2: 類名必須Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        Main main = new Main();
        Set<Integer> result = new HashSet<>();
        int n = scan.nextInt();
        int[] fama = new int[n];
        for(int i = 0; i < n; i++){
            fama[i] =  scan.nextInt();
        }
        main.rese(0,fama,0,0,n,result);
        System.out.println(result.size());
        scan.close();
    }

    public void rese(int a,int[] fama,int sum1, int sum2,int n,Set<Integer> result){
        if(sum1 - sum2 > 0){
            result.add(sum1 - sum2);
        }
        for(int i = a; i < n; i++){
            sum1 += fama[i];
            rese(i+1,fama,sum1,sum2,n,result);
            sum1 -= fama[i];
            sum2 += fama[i];
            rese(i+1,fama,sum1,sum2,n,result);
            sum2 -= fama[i];
        }
    }
}

?前些天發(fā)現(xiàn)了一個(gè)巨牛的人工智能學(xué)習(xí)網(wǎng)站，通俗易懂，風(fēng)趣幽默，忍不住分享一下給大家

跳轉(zhuǎn)到教程

finally，如果讀者們可以理解我這個(gè)解法當(dāng)然我是最開(kāi)心的，雖然在表述上沒(méi)這么清晰吧，但是圖解是我的全部想法，這個(gè)解法也是我自己獨(dú)立想出來(lái)的，感謝您的閱讀！??文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-405453.html

到了這里，關(guān)于藍(lán)橋杯之“砝碼稱重“解題思路，含圖解（Java）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！