1820: 【基础】背包问题求方案数

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：3 解决：2

题目描述

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出 最优选法的方案数。注意答案可能很大，请输出答案模 109+7的结果。


输入

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000

输出

输出一个整数，表示 方案数 模 109+7 的结果。

样例输入 复制 

4 5
1 2
2 4
3 4
4 6

样例输出 复制 

2

提示

#include <iostream>
#include <algorithm>
using namespace std;
const int MOD = 1000000007;
const int MAXN = 1005;
const int MAXV = 1005;

int dp[MAXN][MAXV];
int cnt[MAXN][MAXV];

int main()
{
    int n, vol;
    cin >> n >> vol;
    for(int j = 0; j <= vol; j++)
    {
        dp[0][j] = 0;
        cnt[0][j] = 0;
    }
    cnt[0][0] = 1;

    for(int i = 1; i <= n; i++)
    {
        int v,w;
        cin >> v >> w;
        for(int j = 0; j <= vol; j++)
        {
            dp[i][j] = dp[i-1][j];
            cnt[i][j] = cnt[i-1][j];

            if(j >= v)
            {
                int nv = dp[i-1][j-v] + w;
                if(nv > dp[i][j])
                {
                    dp[i][j] = nv;
                    cnt[i][j] = cnt[i-1][j-v];
                }
                else if(nv == dp[i][j])
                {
                    cnt[i][j] = (cnt[i][j] + cnt[i-1][j-v]) % MOD;
                }
            }
        }
    }
    int maxVal = 0;
    for(int j = 0; j <= vol; j++) maxVal = max(maxVal, dp[n][j]);
    int ans = 0;
    for(int j = 0; j <= vol; j++)
    {
        if(dp[n][j]==maxVal) ans=(ans+cnt[n][j])%MOD;
    }
    cout << ans << endl;
    return 0;
}


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

const int MOD = 1000000007;
const int MAXV = 1005;

int dp[MAXV];
int cnt[MAXV];

int main()
{
    int N, V;
    cin >> N >> V;

    for(int j = 0; j <= V; j++)
    {
        dp[j] = 0;
        cnt[j] = 0;
    }
    cnt[0] = 1;

    for(int i = 1; i <= N; i++)
    {
        int v, w;
        cin >> v >> w;
        for(int j = V; j >= v; j--)
        {
            int new_val = dp[j - v] + w;
            if(new_val > dp[j])
            {
                dp[j] = new_val;
                cnt[j] = cnt[j - v];
            }
            else if(new_val == dp[j])
            {
                cnt[j] = (cnt[j] + cnt[j - v]) % MOD;
            }
        }
    }

    int maxVal = 0;
    for(int j = 0; j <= V; j++)
    {
        maxVal = max(maxVal, dp[j]);
    }

    int ans = 0;
    for(int j = 0; j <= V; j++)
    {
        if(dp[j] == maxVal)
        {
            ans = (ans + cnt[j]) % MOD;
        }
    }
    cout << ans << endl;
    return 0;
}

来源/分类

提交提交记录统计露一手!