B 完全背包

给你$N$个物品

恰好装下体积为$M$ 时的最小价值是多少

max -> min

恰好 -> 初始化为-inf

问题变成了最小，所以必须考虑dp数组的初始化

如果要求恰好$m$ 也必须考虑初始化

所以相比A,其实就是多了初始化,01背包变成了完全背包而已

E.

$n$个数凑出$m$的方案

$n \leq 20$

$2^n$

010101001

$2 \times 2 \times 2 ... = 2^n $

2^10 = 1024 = 1e3 , 2^20 = 1e3 ^ 2 = 1e6

暴力 $O(2^n n)$
- DFS
- 二进制枚举
动态规划,问题变为了01背包求方案数,这只需要更改转移方程
分治FFT,有缘再讲

#include<bist/stdc++.h>

inline int rd() {
    int x;
    scanf("%d",&x);
    return x;
}

int main() {
    int n = rd();
    int m = rd();
    for(int i = 1;i <= n;i++)
        a[i] = rd();
    int ans = 0;
    for(int i = 0;i < (1 << n);i++) {
        int sum = 0;
        for(int j = 0;j < n;j++ ) {
            if((i >> j) & 1) sum += a[j];
        }
        if(sum == m) ans++;
    }
    std::cout << ans;
}

F.

注意到每次物品我们的决策仍然是选或者不选考虑用01背包来做

现在的问题是出现了负数常用的技巧，全体平移

dp[-5000~5000]

dp[5000 * 2]

G

$a_1,a_2..a_n$

$0-a_i$

= M

开摆

动态规划,$dp_{i,j}$表示前$i$个数和为$j$的方案数,转移方程$dp_{i,j} = \sum_{k=0}^{a_i} dp_{i-1,j-k}$
生成函数有缘再讲

H.

特点是数据范围，注意到体积太大，我们设$dp_{i}$ 表示得到价值$i$所需的最小体积

答案就是不超过$W$的最大的$i$

int main()
{
    int n,V;
    int ans = 0;
    scanf("%d%d",&n,&V);
    for(int i = 1;i<=n;++i) 
        scanf("%d%d",&v[i],&val[i]);
    fill(dp,dp + maxn,1e9);
    dp[0] = 0;
    for(int i = 1;i<=n;++i){
        for(int j = 100000;j >= val[i];j--)
            dp[j] = min(dp[j],dp[j-val[i]]+v[i]);
    }
    for(int i = 1;i<=1e5;++i) 
        if(dp[i]<=V) ans = max(ans,i);
    printf("%d\n",ans);
    return 0;
}

动态规划入门题解BEFGH

B 完全背包

E.

F.

G

H.

推荐阅读