题目描述

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

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

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

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

数据范围
0<N,V≤1000
0<vi,wi≤1000

样例

输入样例
4 5
1 2
2 4
3 4
4 6
输出样例：
2

第一次way的初始化不好，没有全部都初始化为一，以为当前体积要可以装下第一个物品，才有1个起点
选择，可是到了第二个时若dp[v] < dp[v - ali[i].v] + ali[i].w，且v - ali[i].v又小于第一个的
体积，那么way就会变成零，所以应该全部初始化为一，这样才不会出现上述情况；
Tips：
而对way的理解就应该是：当前体积下所有的给定数据有多少种方式可以凑出最接近又小于它的数，
这样至少也会有一种方式——什么都不选（0）状态；

C++ 代码

#include<iostream>
#define max(a, b)a > b ? a : b
struct kk
{
    int v, w;
}ali[1007];
const unsigned mod = 1e9 + 7;
int dp[1007] = {};
int way[1007] = {};
int N, V;

int main(void)
{
    scanf("%d %d", &N, &V);
    for (int i = 1; i <= N; i++)scanf("%d %d", &ali[i].v, &ali[i].w);
    for (int v = 0; v <= V; v++)way[v] = 1;//全部初始化为一
    for (int i = 1; i <= N; i++)
        for (int v = V; v >= ali[i].v; v--)
        {
            if (dp[v] == dp[v - ali[i].v] + ali[i].w)way[v] = (way[v] % mod + way[v - ali[i].v] % mod) % mod;
            else if (dp[v] < dp[v - ali[i].v] + ali[i].w)way[v] = way[v - ali[i].v];
            dp[v] = max(dp[v], dp[v - ali[i].v] + ali[i].w);
        }
    printf("%d\n", way[V]);

    return 0;
}