考察点

01背包求最优方案数

二维做法

C++ 代码

#include <iostream>

using namespace std;

const int N=1010;
const int mod=1e9+7;

int v[N],w[N];
int cnt[N][N];   //cnt[i][j] --  从前i个物品里面取，且体积不过j的，能取得最大价值的 方案数
int f[N][N];    // f[i][j] --  从前i个物品里面取，且体积不超过j 的 最大价值
int n,m;

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int j=0;j<=m;j++) cnt[0][j]=1;

    for(int i=1;i<=n;i++)
      for(int j=0;j<=m;j++){

        f[i][j]=f[i-1][j];  // 不取第i个时 的最大价值
        cnt[i][j]=cnt[i-1][j]; //不取第i个时 ,能取得最大价值的方案

        int x=f[i-1][j];
        if(j>=v[i]){  // 取第i个时
            int y=f[i-1][j-v[i]]+w[i];
            // 取时的最大价值与不取时的最大价值作比较
            if(y>x){  
               f[i][j]=y;
               cnt[i][j]=cnt[i-1][j-v[i]];
            }
            else if(y==x)   cnt[i][j]=(cnt[i-1][j-v[i]]+cnt[i][j])%mod;
        }
     }

    cout<<cnt[n][m];
    return 0;
}

一维做法

#include <iostream>

using namespace std;

const int N=1010;
const int mod=1e9+7;

int v[N],w[N];
int cnt[N];  
int f[N];   
int n,m;

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int j=0;j<=m;j++) cnt[j]=1;

    for(int i=1;i<=n;i++)
      for(int j=m;j>=v[i];j--){
        int x=f[j];
        int y=f[j-v[i]]+w[i];
        if(y>x){  
          f[j]=y;
          cnt[j]=cnt[j-v[i]];
        }
        else if(y==x)   cnt[j]=(cnt[j-v[i]]+cnt[j])%mod;
     }

    cout<<cnt[m];
    return 0;
}