01背包问题反思

在01背包中，有两个关键词，”最多”,”最大值”。
现在思考一下：

最大值 -> 最小值 / 方案数

计算值的变更很容易思考，

最大值 -> max();
方案数 -> 情况1 + 情况2；
最小值 -> min();

除此之外，还要考虑 初始值，或者叫边界值；

最大值 -> 0
方案数 -> 1 f[0][0] 代表 有0个物品 选法 只有一种选法 就是啥也不选
最小值 -> +INF ( 2e9 )

最多 -> 正好 / 最少

f[i][j] = count(f[i-1][j],f[i][j-v]+w);
count() -> 状态转移方法

最多 :
f[i-1][j] -> 前i个物品，选择最多为j的集合；
f[i-1][j-v] -> 前i个物品，选择最多为j-v的集合,
这里有个问题：

如果说 当前物品v > j 则会产生
1. 越界
2. 然后实际意义是 第i个物品 无法选择 因为就算只选第i个物品，体积都已经超过规定了。 则要取初始化的值

01背包举例：

for(int j=m;j>=0;j--){
    # 注意 这里没有选择 j>=v
    f[i][j] = max(f[i-1][j],f[i][ max(0,j-v) ]+w); 
}
# 因为初始化的问题 f[i][0] = 0;
而 f[i-1][j] >=0 所以 可以省略为 j>=v;

然后我们扩展来看

正好:
f[i-1][j] -> 前i个物品，选择正好为j的集合；
f[i-1][j-v] -> 前i个物品，选择正好为j-v的集合,

j<v 的实际意义是啥：
集合为空，因为没法选择，所以是默认值 ,代码上也就可以不用循环 直接取i-1的值

最小值:
f[i-1][j] -> 前i个物品，选择最小值为j的集合；
f[i-1][j-v] -> 前i个物品，选择最小值为j-v的集合,

j < v 的实际意义是啥：
前i-1 所有的选法的所有集合，假设 i的物品体积为 100， 但是我们要计算最小50的体积，也就是说我们前i-1的物品随便选择，只要选择第i的物品，就满足了要求。
具体分析
如果是求 最大价值 基本不存在（基本是所有物品相加 不需要dp）
如果是求 方案数 那就是前i-1的所有选法相加 也就是 f[i-1][0] , 因为f[i-1][j] <= f[i-1][0] 且 j>=0
如果是求 最小值 那就是f[i-1][0] 同 方案数

具体题：
数字组合

正好 + 方案数

#include <iostream>
using namespace std;

const int N = 10000 + 7;
int f[N];

int main(){
    int n,m;
    cin >> n >> m;
    f[0] = 1;
    for(int i=1;i<=n;i++){
        int v;
        cin >> v;
        for(int j=m;j>=v;j--){
            f[j] = f[j] + f[j-v];
        }
    }
    cout << f[m] << endl;
    return 0;
}

还有其他的组合
比如 至少 + 最小值 啥的