背包方案数模板题练习

第一道题是另一道也叫做“砝码称重”的前置技能，第二道题是我搜背包方案数的时候出来的。

两道题有一点区别，就是多重（01）背包和完全背包。

第一道题因为数据水，所以多重背包也能过。但是也要学会如何写多重背包！！！

第二道题是完全背包，每一种货币可以拿无穷多次。

这种背包可以理解为价值为0，只有重量。

直接给代码：

第一份的：

#include
    
     const int b[] = {0, 1, 2, 3, 5, 10, 20};int a[7];int weight[100005], tot;int dp[100005];int sum;int main(){    for(int i = 1; i <= 6; i++)    {        scanf("%d", &a[i]);        for(int j = 1; j <= a[i]; j++)        {            weight[++tot] = b[i];        }        sum += a[i] * b[i];    }    dp[0] = 1;    for(int i = 1; i <= tot; i++)    {        for(int j = sum; j >= weight[i]; j--)        {            dp[j] += dp[j - weight[i]];        }    }    int ans = 0;    for(int i = 1; i <= sum; i++) if(dp[i]) ans++;    printf("Total=%d\n", ans);    return 0;}
    

第二份的：

#include
    
     #define ll long longconst int maxv = 26, maxn = 10005;ll weight[maxv];ll dp[1000005];int v, n;int main(){    scanf("%d%d", &v, &n);    for(int i = 1; i <= v; i++)    {        scanf("%lld", &weight[i]);    }    dp[0] = 1;    for(int i = 1; i <= v; i++)    {        for(int j = weight[i]; j <= 10000; j++)        {            dp[j] += dp[j - weight[i]];        }    }    printf("%lld\n", dp[n]);    return 0;}