题目描述

给定n个正整数a[1..n]，求用这些数（每个数可重复使用）凑成总重量c的不同方案数，结果对999983取模。

解题思路

本题为完全背包问题，使用动态规划求解。定义f[j]为凑成重量j的方案数，初始状态f[0]=1（凑0的方案数为1，即空集）。对于每个物品a[i]，通过内层循环从a[i]到c遍历，更新f[j] += f[j - a[i]]，确保每个物品可被多次使用。最后输出f[c]即为答案。

#include<bits/stdc++.h>
using namespace std;
int f[110000], a[110];
int main()
{
    memset(f, 0, sizeof(f));f[0]=1;
    int n,c;scanf("%d%d",&n,&c);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {   
        for(int j=a[i];j<=c;j++)
			f[j] = (f[j] + f[j - a[i]]) % 999983;
    }
    printf("%d\n",f[c]);
    return 0;
}