AcWing_11. 背包问题求方案数_dp

AcWing_11. 背包问题求方案数_dp

//
#include
using namespace std;
 
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
const int N=1111;
int x[N],y[N],dp[N],plan[N];
 
int main()
{
    int n,v,i,j,tt,sum,maxx,ans;
 
    while( cin>>n>>v )
    {
        for( i=1;i<=n;i++ ) cin>>x[i]>>y[i];
//		for( i=0;i
		memset( dp,0,sizeof( dp ) );
		
        plan[0]=1;									// init_不放物品_是没有物品时的最优解 
        for( i=1;i<=n;i++ )
            for( j=v;j>=x[i];j-- )					// 01背包_逆序 
            {
                tt=max( dp[j],dp[j-x[i]]+y[i] );
                sum=0;								// 如果当前物品放与不放都是最优解 则方案数是他们的和
													// 所以才会出现两个if 而不是if...else if 
                if( tt==dp[j] )         	sum+=plan[j];
                if( tt==dp[j-x[i]]+y[i] ) 	sum+=plan[j-x[i]];
									// +y[i]
                dp[j]=tt;
                plan[j]=sum%MOD;	// %MOD_pos
            }
        maxx=-INF;									// 找到最优解 
        for( i=0;i<=v;i++ ) maxx=max( maxx,dp[i] );
 
        ans=0;						// dp[i]==maxx
        for( i=0;i<=v;i++ )							// 和最优解相同 进行累和_取模 
            if( dp[i]==maxx ) ans=( ans+plan[i] )%MOD;
        cout<
    }
    return 0;
}
// Q: 为什么累加取模 ?
// A: 举个例子
 
    // V==3
 
    // id x y
    // 1 2 10
    // 2 3 10
 
    // dp[1]=0;
    // dp[2]=10;
    // dp[3]=10;
 
    // plan[1]=plan[2]=plan[3]=1;
 
    // ans=1+1=2;