题目描述

blablabla

样例

blablabla

背包问题求方案数

C++ 代码

#include <iostream>
using namespace std;
#include <cstring>
#include <algorithm>

int n,v;
int vi[1001],wi[1001];
int dp[1001],num[1001];
const int mod=1e9+7;
int main(){
    int i,j;
    while(cin >> n >> v){
        for(i=1;i<=n;++i){
            cin >> vi[i] >> wi[i];
        }
        for(i=0;i<1001;++i){
            num[i] = 1;
        }
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;++i){
            for(j=v;j>=vi[i];--j){
                if(dp[j]<dp[j-vi[i]]+wi[i]){   ///当加入当前物品价值更大
                    dp[j]=dp[j-vi[i]]+wi[i]; ///当前价值修改
                    num[j]=num[j-vi[i]]%mod; ///当前价值的数目也修改
                }else if(dp[j]==dp[j-vi[i]]+wi[i]){///找到与最大价值一样的
                    num[j]=(num[j-vi[i]]+num[j])%mod;///最大价值数目增加
                }
            }
        }
        cout << num[v] << endl;
    }
    return 0;
}

用两个数组 一个是dp[j]代表j体积最大价值
一个是num[j]代表j体积最大价值的方案数