11. 背包问题求方案数 - AcWing题库

分析：需要求最优解的方案数，其实也是一个动态规划的过程

• 首先求出背包问题的最优解
• 动态规划求方案数

 

状态计算：

根据最后一个不同点进行划分，也就是对于a[i]的选择情况进行划分

• 选的情况优于不选       cnt[i,j]=cnt[i-1,j-v]
• 选的情况==不选          cnt[i,j]=cnt[i-1,j]+cnt[i-1,j-v]
• 选的情况<不选            cnt[i,j]=cnt[i-1,j]

初始化：由于是至多为j，那么cnt[0][i]=1

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1005;
const int mod=1e9+7;
typedef long long ll;
int dp[N];
ll cnt[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<=m;i++)
        cnt[i]=1;
    for(int i=1;i<=n;i++)
    {
        int v,w;
        cin>>v>>w;
        for(int j=m;j>=v;j--)
        {    
            int value=dp[j-v]+w;
            if(value>dp[j])
                dp[j]=value,cnt[j]=cnt[j-v]%mod;
            else if(value==dp[j])
                cnt[j]=(cnt[j]+cnt[j-v])%mod;
            //else if ... dp[j]=dp[j];
        }
    }
    
    cout<<cnt[m];
    return 0;
}

如果状态表示是恰好为j的话

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
typedef long long ll;
const int mod=1e9+7;
int dp[N];
ll cnt[N];
int main()
{
    int n,m;
    cin>>n>>m;
    cnt[0]=1;
    for(int i=0;i<n;i++)
    {
        int v,w;
        cin>>v>>w;
        for(int j=m;j>=v;j--)
        {
            int value=dp[j-v]+w;
            if(value>dp[j])
                dp[j]=value,cnt[j]=cnt[j-v]%mod;
            else if(value == dp[ j ])
                cnt[j]=(cnt[j]+cnt[j-v])%mod;
        }
    }
    int res=0;
    for(int i=0;i<=m;i++)
        if(dp[i]==dp[m])
            res=(res+cnt[i])%mod;
    cout<<res;
    return 0;
    
}