搜索(30pts)

• 通过搜索枚举每种物品的选项，然后累加所有的答案

#include<bits/stdc++.h>
using namespace std;
const int N=110,MOD=1000007;
int n,m;
int a[N];
int dfs(int x,int k)
{
	if(k>m) return 0;
	if(k==m) return 1; //找到了一种解法 
	if(x==n+1) return 0; //已经搜索完了 
	int ans=0;
	for(int i=0;i<=a[x];i++) //枚举第x中花的选择数 
	{
		ans=(ans+dfs(x+1,k+i))%MOD; //累加所有的方案 
	}
	return ans; //返回方案数 
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
    	cin>>a[i];
	}
	cout<<dfs(1,0)<<endl;
    return 0;
}

二维动态规划(100pts)

• f[i][j]表示在前$i$种物品中选，体积恰好为$j$的最大价值
• 状态计算 $f[i][j]=(f[i][j]+f[i-1][j-k])$

#include<bits/stdc++.h>
using namespace std;
const int N=110,MOD=1000007;
int f[N][N]; //f[i][j]表示在前i种数种选，和为j的方案数目
int a[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
    	cin>>a[i];
	}
	f[0][0]=1;
	for(int i=1;i<=n;i++) //枚举每种物品
	{
	    for(int j=0;j<=m;j++) //枚举当前的和
	    {
	        for(int k=0;k<=min(j,a[i]);k++) //枚举当前物品的每种选项
	        {
	            f[i][j]=(f[i][j]+f[i-1][j-k])%MOD;
	        }
	    }
	}
	cout<<f[n][m]<<endl;
    return 0;
}

多重背包问题优化

• f[j]表示在前$i$个物品中选,体积为$j$的方案数

#include<bits/stdc++.h>
using namespace std;
const int N=110,MOD=1000007;
int f[N];
int main()
{
    int n,m;
    cin>>n>>m;
    f[0]=1;
    for(int i=1;i<=n;i++) //枚举每个物品
    {
        int a;
        cin>>a;
        for(int j=m;j>=0;j--) //从大到小枚举虚拟体积
        {
            for(int k=1;k<=a&&k<=j;k++) //枚举物品的选择
            {
                f[j]=(f[j]+f[j-k])%MOD;
            }
        }
    }
    cout<<f[m];
    return 0;
}