背包问题相信大家都不陌生，以前我接触过的背包问题是主要是0-1背包以及普通背包问题。
今天，介绍一种也是比较基本的类型——完全背包。

一、完全背包

题目引入

设有物品N种，其重量为Weight[N]，价值为Value[N]。现有容量为M的背包，若这N种物品各有无限多个，求该背包可装物品的最大价值为多少？
设dp[N][M]，代表前N种物品在容量为M的背包中可产生的最大价值。
若题目没有 “若这N种物品各有无限多个” 这一条件，该问题就转化为了简单的0-1背包问题，在这种情况下：
dp[i][j] = max( dp[i-1][j]，dp[i-1][j-Weight[i]]+Value[i] )，
即此时dp[i][j]要么由不放入第i种物品产生，要么放入第i种物品产生，求得两种情况的最大值即可；

但对于题目所给的条件，我们需要考虑第i种物品被放入了几件，故在这种情况下：
dp[i][j] = max( dp[i-1][j]，dp[i-1][j-k * Weight[i]] +k * Value[i] ),
根据该动规方程易得循环

for( i=1; i<=N; i++) 
   for( j=1; j<=M; j++)
        for(k=1;k*Weight[i]<=j;k++)
       {
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-k*Weight[i]]+k*Value[i]);
       }

代码优化（降维）

通过观察该方程，我们可以发现，dp[i][j]只与本行在其之前的以及其正上方的元素值有关。因此可向一维数组进行转化。
设f[j]为容量为j的背包可装的最大价值，最后一次装入背包的是weight[i],有：
f[j] = max( f[j], f[j−Weight[i]]+Value[i] ),
因此可得简化后的代码

for( i=1; i<=N; i++) 
   for( j=1; j<=M; j++)
    {
        f[j] = max( f[j], f[j−Weight[i]]+Value[i] )；
    }

二、变式——自然数拆分的方案数

（补充：本题中6=6是合法的）
本题目有多种解法，具体使用哪一种要根据N的范围来确定。如回溯法（1——50左右）等，代码放在文章最后。这里以完全背包的解法为例。

完全背包解法

设dp[i][j]为值为j的数，被拆分成1~i的方案和。

进行代码优化，dp[j]代表数j的分解方式的个数。容量为j的背包，每次放入体积为i的物品：

for( i=1; i<=N; i++) 
   for( j=1; j<=N; j++)
    {
        //dp[j]+=dp[j−Weight[i]]；
        dp[j] = dp[j] + dp[j−i]；//Weight[i]==i
    }

以n=3为例，三轮循环结束后，可以得到dp[3]=dp[2]+dp[1]+dp[0].
完整代码如下：

#include<stdio.h>
#include <string.h>
#define maxn 4005
const int mod=2147483648;

long long dp[maxn];
int num,n;
int main()
{

    scanf("%d",&num);
    while(num--)
    {
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            for(int j=i;j<=n;j++)
            {
                dp[j]=(dp[j]+dp[j-i])%mod;
            }
        }
        printf("%lld\n",dp[n]%mod );
    }
    return 0;
}

学习参考：https://blog.csdn.net/nuist_Jiang/article/details/86594323

补充：回溯法

#include<stdio.h>

int n;
int x[55]={0};
int c;

void backtrace(int t)
{    
    if(c==n)
    {
        printf("%d=%d",n,x[1]);
        for(int i=2;x[i]!=0;i++)
        {
            printf("+%d",x[i]);
        }
        printf("\n");
    }
    else
    {
        for(int i=1;i<=n-t+1;i++)
        {
            if(c+i<=n&&i>=x[t-1])
            {
                x[t]=i;
                c+=i;
                backtrace(t+1);
                x[t]=0;
                c-=i;
            }
            //printf("%d\n",t);
        }

    }
}

int main()
{
    scanf("%d",&n);
    c=0;
    backtrace(1);
    return 0;
}