砝码称重问题二

length_n=len(w)
S=set([])
S.add(0)
for i in range(length_n):
    temp_S=S.copy()
    for s in temp_S:
        j=1
        while j<=n[i]:
            S.add(s+j*w[i])
            j+=1
#print S 
print len(S)

    public int backPack2(int[]A,int []B){
        int total = 0;
        for(int i=0;i)
            total +=A[i]*B[i];
        TreeSet set = new TreeSet();
        set.add(total);
        for(int i=0;i){
            Object[] setCopy = set.toArray();
            for(Object s:setCopy){
                int j = 1;
                while(j<=B[i]){
                    set.add(((Integer)s-j*A[i]));
                    j++;
                }
            }
        }
        for(Integer s:set){
            System.out.print(s+" ");
        }
        return set.size();
    }

    /**
     * A[i] 第i个砝码的重量
     * B[i] 第i个砝码的数量
     * @param A
     * @param B
     * @return
     */
    public int backPack3(int[]A,int []B){
        int total = 0;
        for(int i=0;i)
            total +=A[i]*B[i];
        boolean dp[] = new boolean[total+1]; // dp[i] = true 表示可以称出质量为 i 的重物 
        dp[0] = true; 
        for(int i=0;i// 砝码重量
            for(int j = 0;j<=B[i];j++){// 对 第 i个砝码遍历其种类
                for(int s=total;s>=A[i];s--){ // 砝码的总重量开始遍历，为什么？ total -- A[i] 的质量是否能够称出 能否称出体现着 s-A[i]能否称出
                    if(dp[s - A[i]]) // dp[s - A[i]] = true 就是可以称出 s - A[i]的重物，也就是可以称出 s - A[i] + A[i] 的重物 
                        dp[s] = true;
                }
            }
        }
        int count = 0;
        for(int i = 0;i){
            if(dp[i]){
                System.out.print(i+" ");
                count++;
            }
        }
        return count;
    }