初始化总结

1. 体积最多是j：全部 状态 初始化为0（ 只会求最大值 ）
2. 体积恰好是j：
   • 求最小值： dp[0][0]=0，其余状态初始化为INF
   • 求最大值： dp[0][0]=0，其余状态初始化为INF
3. 体积至少是j： 全部状态初始化为INF，仅dp[0][0]=0（只会求最小值）

总结： 背包问题，若体积规定上限，则不用特别管 ；若体积规定刚好等于或规定了下限，则初始化dp[0][0]，其他根据求最大值还是最小值初始化为INF或-INF

3种背包总结

1. 完全背包问题（物品可以随便选）相对0-1背包问题，修改第二个状态转移方程即可
   dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i])→ dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i])
2. 完全背包，0-1背包，多重背包都可以看作多重背包问题
   • 0-1背包，物品数只有一件
   • 完全背包，在体积上限规定的情况下，物品数上限为k（需计算得到）
   • 多重背包，物品数上限为k
     然后采用二进制打包的方式，将完全背包和多重物品打包好即可
3. 多维限制一样都可以用，多开一重循环就好

    int cnt=0;
    while(n--){
        int a,b,c;
        cin>>a>>b>>c;
        for(int j=1;j<=c;j*=2){
            v[++cnt]=j*a;
            w[cnt]=j*b;
            c-=j;
        }
        if(c>0){
            v[++cnt]=c*a;
            w[cnt]=c*b;
        }
    }

属性为cnt的背包问题的总结

1. dp数组要开unsiged long long
2. dp[i][j]表示只考虑前i件物品，体积为j的方案数
3. dp[i][j]每次更新时，都要取模dp[i][j]%mod
4. 初始化：dp[0][0]=1：只考虑前0件物品，体积为0的方案数为1
5. 0-1背包与 完全背包的性质在这里也适用