01背包问题

二维的dp数组的列给小了，起码得10001才行

感谢

请问朴素写法的j为什么要从0开始

个人理解，权当给同学们一个靶子，抛砖引玉吧：
其实为什么j要从0开始，是一种代码变形的结果，因为大家不知道原始的形态是什么样的，所以有困惑，原始形态是这样的：

#include <bits/stdc++.h>

using namespace std;
const int N = 110;
const int M = 10010;
int n, m;
int a[N];
int f[N][M];

int main() {
    scanf("%d %d", &n, &m);

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

    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        for (int j = 1; j <= m; j++) {
            f[i][j] = f[i - 1][j];
            if (j >= a[i]) f[i][j] += f[i - 1][j - a[i]];
        }
    }
    printf("%d\n", f[n][m]);
    return 0;
}

为什么要用循环初始化掉左侧第一列呢？因为使用瞪眼大法知，每一个状态，都是从上一行的前序状态转移而来，而递推值开始不能是0（原因可以参考下面咸鱼兄弟问题我的回答），只能是1，也就是左侧第一列全要给初始值1.之所以现在写成j=0，其实是把原始形态的代码进行了等价变形，这样代码更短，当然，如果你不习惯这样写，按我的写法也是一样的。算法这东西，细节在搞懂之后，就需要背诵一些内容了，背的时间长了，随手就可以写出来，写出来也就对了，代码还短。但必须要搞清楚细节，否则背诵下来是没有灵魂的~

因为f[i][0]需要计算，以推出后面的状态，如果不从0开始，那么默认值是0显然不对（从前i个物品选，体积恰好等于j的方案就是1个，即什么都不选）

请问为什么f[0][0]要等于1呢

从前0个数中选，且总和不超过0，显然仅有一种方案即什么都不选，而f[i][j]表示的是方案的数目，故f[0[0] = 1;

使用瞪眼大法（观察法）观察状态转移方程可知，一个新状态$f[i][j]$，要么从$f[i - 1][j]$转移过来，要么从$f[i - 1][j - a[i]]$转移而来，而我们定义的属性是方案数，所以采用了累加的办法就可以了。这样从大到小去思考，是不是就是大的依赖小的，小的依赖更小的，那么最小的就是$f[0][0]$,如果它是$0$，那么，我们就会发现一个很滑稽的结论，$0$不管怎么累加都是$0$，最后就加了个寂寞~，似乎与乘法世界的本原是$1$概念是一样的，比如我们要计算累乘积，一定是定义初始值$s=1$,然后再s=*2,s=*3,s*=4,你把$s$定义成$0$试试，也是乘了个寂寞。

哈哈好的蟹蟹

好的 蟹蟹

二维的，他这应该写错了

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        int[] a = new int[5010];
        int[][] dp = new int[5010][10010];

        for(int i=1; i<=n; i++){
            a[i] = scan.nextInt();
        }
        dp[0][0] = 1;

       for (int i = 1; i <= n; i ++ ){
        for (int j = m; j >= 0; j -- ){
           dp[i][j]=dp[i-1][j];
           if(j>=a[i])
           dp[i][j]+=dp[i-1][j-a[i]];
       }
      }

        System.out.println(dp[n][m]);
    }
}

没错

二维的为什么j不能从1开始?

二维的为什么j不能从1开始?

有点小问题，应该f[i][0]都初始化为1才对， 我试了，不然ac不了

#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
using namespace std;

const int N = 10010;
int f[110][N];
int v[110];
int n, m;

int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);

cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> v[i];
f[0][0] = 1;
for (int i = 1; i<= n; i++)
{
    f[i][0] = 1;
    for (int j = 1; j <= m; j++)
    {
        f[i][j] = f[i - 1][j];
        if (j >= v[i]) f[i][j] += f[i - 1][j - v[i]];
    }
}

cout << f[n][m] << endl;
return 0;

}

加不加无所谓吧，都可以过

呜呜呜终于懂了二维到一维的转换了，谢谢大佬QAQ

给出二维的属实对我们菜鸡贴心