我觉得不是不超过，是因为cnt数组降成一维后迷惑性太明显，如果用二维解释就通了，实际上初始化的是没有物品即物品数量=0时候的1-V体积的方案数，因为没有物品，所以方案就是什么都不放（1一种方案），最优价值为0

#include<iostream>

using namespace std;

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

int dp[maxn][maxn],count[maxn][maxn];
int main(){
    int N,V,v,w;

    cin>>N>>V;
    for(int i = 0;i<=V;i++){
        count[0][i] = 1;
    }
    for(int i = 1;i<=N;i++){
        cin>>v>>w;

        for(int j = V;j>=0;j--){
            if(j<v) {
                count[i][j] = count[i-1][j];

                dp[i][j] = dp[i-1][j];
            }
            else {
                if(dp[i-1][j-v]+w>dp[i-1][j]) 
                    count[i][j] = count[i-1][j-v];
                else if(dp[i-1][j-v]+w==dp[i-1][j])
                    count[i][j] = (count[i-1][j]+count[i-1][j-v])%mod;
                else 
                    count[i][j] = count[i-1][j];

                dp[i][j] = max(dp[i-1][j],dp[i-1][j-v]+w);
            }
        }       
    }
    cout<<count[N][V]<<endl;
    return 0;
} 

之后再降成一维

请问这个初始化为啥是for(int i=0;i<=m;i++) cnt[0][i]=1;

0种物品无论空间多少只有一种方案就是不放

f[i][j]，g[i][j]的含义是什么呢

我也觉得博主的写法是定义cnt[i]为不超过时候的方案数。如果定义成恰好，初值和答案部分应该是像y总那样。

我觉得背包体积为i与物品体积不超过i是等价的,博主说的是背包体积为i,但没说要刚好选满i体积的物品

没看题解写了一个不超过的的代码，和博主的代码一样的，感觉这题不超过反而好写~

这个题解到底有什么问题？看不出来，气死人了

太吊了

memset(cnt,1,sizeof cnt);
为什么这样初始化就不行呢哎

memset是按字节赋值，每个int是4个字节，这样会赋值成00000001000000010000000100000001

大佬这样会有什么区别吗？不还是1吗？

这个数当然不是1，1是00000000000000000000000000000001

懂了懂了，谢谢大佬

ac不了啊

能啊

为什么我用这个代码提交wa了啊

%%%

Orz

能帮我看看二维的哪错了吗

二维的有什么问题？

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int cnt[N][N], f[N][N];
int v[N], w[N];

int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        scanf("%d%d", &v[i], &w[i]);
    }
    memset(cnt, 1, sizeof cnt);

    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= m; j++) {
            int value = f[i - 1][j];
            if(j >= v[i]) {
                if(value > f[i - 1][j - v[i]]) {
                    f[i][j] = value;
                    cnt[i][j] = cnt[i - 1][j];
                }else if(value == f[i - 1][j - v[i]]) {
                    f[i][j] = value;
                    cnt[i][j] = (cnt[i - 1][j] + cnt[i - 1][j - v[i]]) % mod;
                }else {
                    f[i][j] = f[i - 1][j - v[i]];
                    cnt[i][j] = cnt[i - 1][j - v[i]];
                }
            }else {
                f[i][j] = value;
                cnt[i][j] = cnt[i - 1][j];
            }
        }
    cout << cnt[n][m] << endl;
    return 0;
}

你去看看memset的用法.....

这个memset和我以前一样了，hh

memset初始化不能赋值1

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int cnt[N][N], f[N][N];
int v[N], w[N];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &v[i], &w[i]);
    }
    // memset(cnt, 1, sizeof cnt);
    for (int i = 0; i < N; i++) cnt[i][0] = 1;
    for (int i = 0; i < N; i++) cnt[0][i] = 1;

    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++) {
            int value = f[i - 1][j];
            if (j >= v[i]) {
                if (value > f[i - 1][j - v[i]]+w[i]) {
                    f[i][j] = value;
                    cnt[i][j] = cnt[i - 1][j];
                } else if (value == f[i - 1][j - v[i]]+w[i]) {
                    f[i][j] = value;
                    cnt[i][j] = (cnt[i - 1][j] + cnt[i - 1][j - v[i]]) % mod;
                } else {
                    f[i][j] = f[i - 1][j - v[i]]+w[i];
                    cnt[i][j] = cnt[i - 1][j - v[i]];
                }
            } else {
                f[i][j] = value;
                cnt[i][j] = cnt[i - 1][j];
            }
        }
    cout << cnt[n][m] << endl;
    return 0;
}

为什么这里用memset不对

现在是第一行第一列设置为1，不是全都是1、

我发现一个问题，就是acwing里面的所有数据好像都有点弱，😄

博主的f[i]用来存储背包容积为i时的最佳方案的总价值，但如果设置成体积恰好为i的话不应该初始化f[i]为负无穷吗，因为不能保证所的f[i]都被凑出来，这里是不是应该写成体积不超过i

容器恰好v相当于体积不超过v

😢如果01背包求解体积恰好是i的最大价值不应该初始化吗

我个人感觉这里的题解是有问题的，博主的状态定义是恰好，结果却写了不超过的代码。如果状态是 体积恰好是v，那么只用初始化cnt[0] = 1，如果状态定义是 体积不超过v，那么就需要 for (int i = 0; i < v; ++i) cnt[i] = 0了

容器恰好v相当于体积不超过v

转移方程是一样的，算最后答案的时候是不一样的

只在cnt[0]赋值成1为什么不对呀。

因为背包问题的$f[i]$是背包容积为$i$的时候的最大价值，相应的$cnt[i]$是背包容积为$i$的时候的凑成最大价值的方案数，无论容积是多少，什么都不装都是一种方案，所以当然要都初始化为1

滑稽佬，这cnt[j] = (cnt[j] + cnt[j - v]) % mod;不会有重复吗，如果是不大于j的话

不会吧，cnt[ j - v ] 是 i - 1 个物品中选，应该不会重复

cnt[j]是上一层的体积为[j],那时候还没有选第i件物品的方案，没有重复~

感觉数据弱了，我初始化不小心写成

for (int i = 0; i <= n; i ++) cnt[i] = 1;

也过了

%%%

背包里什么也不装也是一种方案

我漏掉这个了，怪不得算的不对