問題描述

???????Mike is a lawyer with the gift of photographic memory. He is so good with it that he can tell you all the numbers on a sheet of paper by having a look at it without any mistake. Mike is also brilliant with subsets so he thought of giving a challange based on his skill and knowledge to Rachael. Mike knows how many subset are possible in an array of N integers. The subsets may or may not have the different sum. The challenge is to find the maximum sum produced by any subset under the condition:

The elements present in the subset should not have any digit in common.

Note: Subset {12, 36, 45} does not have any digit in common and Subset {12, 22, 35} have digits in common.Rachael find it difficult to win the challenge and is asking your help. Can youhelp her out in winning this challenge?

輸入

???????First Line of the input consist of an integer T denoting the number of test cases. Then T test cases follow. Each test case consist of a numbe N denoting the length of the array. Second line of each test case consist of N space separated integers denoting the array elements.

Constraints:
1 <= T <= 100
1 <= N <= 100
1 <= array elements <= 100000

輸出

???????Corresponding to each test case, print output in the new line.

示例輸入

1
3
12 22 35

示例輸出

57

思路

int[ ] s :輸入的數(shù)字
boolean[ ] visited：0~9是否已被訪問
i：考慮第i個數(shù)

???????第i層遞歸：考察第i個數(shù)的各位數(shù)字是否都沒被訪問。若是則此數(shù)可能是最終結(jié)果之一，此時有兩種情況：1.選中此數(shù)；2.不選此數(shù)。若否，則只有1種情況，即上述情況2。這兩種情況可通過m1、m2計算：
???????m1=該數(shù)+（第i+1層遞歸的結(jié)果，將該數(shù)的各位設(shè)置為已訪問）
???????m2=第i+1層遞歸的結(jié)果，將該數(shù)的各位設(shè)置為未訪問
???????最后返回m1、m2中較大者

使用動態(tài)規(guī)劃改進

???????遞歸的解法存在重復(fù)計算，通過動態(tài)規(guī)劃改進之。每次遞歸計算所依賴的參數(shù)有兩個：i、visited數(shù)組。（輸入數(shù)組s沒有改變，可視作全局變量）。直觀地，可構(gòu)建dp數(shù)組為dp[i.length][2][2][2][2][2][2][2][2][2][2]，但在編程時可使用更簡便的方法：將后面的10個2壓縮到1個維度，即dp[i.length][2^10]。此時第2個維度上的取值范圍是0~1023，將其看作二進制數(shù)，則每一位上1表示已訪問，0表示未訪問。
???????使用動態(tài)規(guī)劃優(yōu)化遞歸過程的方式為：在進行第i次遞歸時，先查找dp矩陣看當前參數(shù)下的結(jié)果是否已經(jīng)被計算，若已計算則直接返回之，否則按照上述過程計算，并在返回結(jié)果之前更新dp矩陣。

代碼

import java.util.*;
import java.lang.*;

class Main{
    public static int func(String[] s, int n, int i, boolean[] visited, int[][] dp)
    {
        //已考慮了全部n個數(shù)
        if(i==n)
        {
            return 0;
        }
        //mask就是壓縮后的維度2
        int mask=0;
        for(int y=0;y<10;y++)
        {
            if(visited[y])
            {
                mask+=Math.pow(2,y);
            }
        }
        if(dp[i][mask]!=-1)
        {
            return dp[i][mask];
        }
        String current=s[i];
        int flag=0;
        int temp[]=new int[10];
        for(int k=0;k<current.length();k++)
        {
            //char轉(zhuǎn)int要減48，也可以先轉(zhuǎn)為String再轉(zhuǎn)為int
            int num=(int)current.charAt(k)-48;
            if(visited[num])
            {
                flag=1;
                break;
            }
            temp[num]=1;
        }
        int m1=0;
        int m2=0;
        if(flag==0)
        {
            //選中第i個數(shù)（在可以選的情況下），則修改visited并遞歸計算
            for(int k=0;k<10;k++)
            {
                if(temp[k]==1)
                {
                    visited[k]=true;
                }
            }

            m1=Integer.parseInt(s[i])+func(s,n,i+1,visited,dp);
            //不選擇第i個數(shù)，則先還原visited
            for(int k=0;k<10;k++)
            {
                if(temp[k]==1)
                {
                    visited[k]=false;
                }
            }
        }
        //還原后再遞歸計算
        m2=func(s,n,i+1,visited,dp);
        //比較二者、更新dp矩陣
        return dp[i][mask]=Math.max(m1,m2);
    }
    public static void main (String[] args) {
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        for(int j=0;j<t;j++)
        {
            int n=sc.nextInt();
            String s[]=new String[n];
            for(int i=0;i<n;i++)
            {
                s[i]=sc.next();
            }
            boolean visited[]=new boolean[10];
            int dp[][]=new int[n][1024];
            for(int i=0;i<n;i++)
            {
                for(int k=0;k<1024;k++)
                {
                    dp[i][k]=-1;
                }
            }
            System.out.println(func(s,n,0,visited,dp));
        }
    }
}

python代碼

t = int(input())
for _ in range(t):
    n = int(input())
    S = input().strip().split()
        
    A = []
    for s in S:
        m = 0
        for ss in set(s):
            m += 1 << int(ss)
        A.append((int(s), m))
    
    A.sort(key=lambda x: x[1])

    AA = []
    i = 0
    n = len(S)
    while i < n:
        a,m = A[i]
        i += 1
        while i < n and A[i][1] == m:
            if A[i][0] > a: a = A[i][0]
            i += 1
        AA.append((a,m))

    mx = 0
    R = [(0,0)]
    while R:
        RR = []
        for r,m in R:
            if m == 0b1111111111:
                continue
    
            for a,am in AA:
                if m & am == 0:
                    rr = r + a
                    if rr > mx: mx = rr
                    RR.append((rr, m+am))
    
        RR.sort(key=lambda x: x[1])
        R = []
        i = 0
        nn = len(RR)
        while i < nn:
            r,m = RR[i]
            i += 1
            while i < nn and RR[i][1] == m:
                if RR[i][0] > r: r = RR[i][0]
                i += 1
            R.append((r,m))
    
    print(mx)