第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-936 砝码称重

#include<stdio.h>
#include<string.h>
int num[111],val[111];
int c1[10000+100],c2[10000+100];
#define mod 100000007;
int main()
{   int num1=0;
	int n,i,j,k,sum;
	while(scanf("%d",&n)!=EOF)
	{
		sum=0;
		memset(num,0,sizeof(num));
		for(i=1;i<=n;i++)
		{
			scanf("%d",&val[i]);
			num[val[i]]=1;
			sum+=val[i];
		}
			memset(c1,0,sizeof(c1));
			memset(c2,0,sizeof(c2));
			for(j=0;j<=val[1]*num[val[1]];j+=val[1])//限制了每种的个数 最多为 num[val[i]]*val[i]     由于本题都是1 可以去掉不写
				/*如 质量为1 的砝码有4个  则母函数第一个式子为为 1+x^1+x^2+x^3+x^4*/
				c1[j]=1;
			for(i=2;i<=n;i++)
			{
				for(j=0;j<=sum;j++)//指向上一次已经计算过的式子的项
					for(k=0;k+j<=sum&&k<=num[val[i]]*val[i];k+=val[i])//限制了每种的个数就要这样写了
					{//k指向当前要成的式子的项
						c2[k+j]+=c1[j]%mod;
						c2[k+j]%=mod;
					}
					for(k=0;k<=sum;k++)
					{
						c1[k]=c2[k]%mod;
						c2[k]=0;
					}
			}
			for(i=1;i<=sum;i++)
                if(c1[i])
                    num1=num1+1;
            printf("%d",num1);
            //for(i=1;i<=sum;i++)
			//	if(c1[i])
			//	printf("%d %d\n",i,c1[i]);

	}
	return 0;

}

#include<bits/stdc++.h>
using namespace std;
int dp[105][100006]={0};  //动态规划数组
int a[105];     //砝码数组
int main()
{
    int n,sum=0;
    int ans=0;
    cin>>n;      //砝码数量
    for(int i=0;i<n;i++)
    {
        cin>>a[i];         //输入每个砝码重量
        sum+=a[i];         //确定每次遍历循环的最大值
    }
    dp[0][a[0]]=1;          //第一个砝码的重量一定可以被称出来
    int x;                 
    for(int i=1;i<n;i++)   //从第二个砝码开始动态规划
    {
        x=a[i];            //当前加入砝码的重量
        for(int j=1;j<=sum;j++)
        {
            dp[i][j]=dp[i-1][j];  //复制前一组状态
        }
        dp[i][x]=1;          //当前砝码一定可以被称出来
        for(int j=1;j<=sum;j++)
        {
            if(dp[i-1][j])   //在上一状态的基础上加入一个新的砝码
            {                //只需考虑上一状态的每个可以被称出的重量与当前砝码的组合
                dp[i][j+x]=1; 
          
            }
        }
    }
    for(int i=1;i<=sum;i++)   //将最后的状态遍历计数，即为可称出的重量的数量
        if(dp[n-1][i])  ans++;
    cout<<ans;
    return 0;
} 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Main {
    static Set set;

    public static void main(String[] args) throws IOException {
        set = new HashSet();
        StreamTokenizer s = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        s.nextToken();
        int n = (int) s.nval;
        int[] arr = new int[n];
        int sum = 0;
        Arrays.sort(arr);
        for (int i = 0; i < n; i++) {
            s.nextToken();
            arr[i] = (int) s.nval;
            sum += arr[i];
        }
        int target = sum;
        dfs(arr, 0, target);
        System.out.println(set.size());
    }

    private static void dfs(int[] arr, int cur, int k) {
        if (k > 0) {
            set.add(k);
        }

        if (k < 0 || cur == arr.length) return;

        //不选
        dfs(arr, cur + 1, k);

        //选
        dfs(arr, cur + 1, k - arr[cur]);


    }
}

def dfs(index: int, lst: list, limit: int):
    if index > limit-1:
        return
    for i in range(index, limit):
        lst.append(maple[i])
        res.add(sum(lst))
        index += 1
        dfs(index, lst, limit)
        lst.pop()
n = int(input())
maple = list(map(int, input().split()))
res = set()
dfs(0, maple, n)
print(len(res))