首页 程序设计 动态规划 背包问题

# 题目大意

有 nn 种物品和一个容量是 vv 的背包
第 ii 种物品的体积是 viv_i，价值是 wiw_i，有 sis_i 件
问：你放进背包的最大价值是多少

# 数据范围

  • 小范围（多重背包 II）
    • 0<N,V≤10000 < N, V \le 1000
    • 0<vi,wi≤10000 < v_i, w_i \le 1000
  • 大范围（多重背包 IIII）
    • 0<N≤10000 < N \le 1000
    • 0<V≤20000 < V \le 2000
    • 0<vi,wi≤20000 < v_i, w_i \le 2000

# 思路

# 小范围

对于小范围的多重背包，直接类似完全背包的三维思路，将第三维改成枚举 kk 个第 ii 种物品即可

C++
1
2
3
4
5
6
7
8
9
10
11
12
void solve () {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i] >> s[i];

    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
            for (int k = 0; j >= k * v[i] && k <= s[i]; k++)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);
                
    cout << dp[n][m] << endl;
}

# 大范围

对于大范围的多重背包，应将多重背包进行二进制拆分，从而转换成 0101 背包

对于任意一个数 nn，他一定能分解成
n=1+21+22+...+2t+resn = 1 + 2^1 + 2^2 + ... + 2^t + res
而对于 1→n1 \to n 的任意一个数，都能从这里面抽若干个构成，从而可以构成 0101 背包

利用 0101 背包的一维写法，得出以下代码

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve () {
    cin >> n >> m;
    for (int i = 1, vv, ww, ss; i <= n; i++) {
        cin >> vv >> ww >> ss;

        int t = 1;
        while (t <= ss)
            ++cnt, v[cnt] = t * vv, w[cnt] = t * ww, ss -= t, t *= 2;
        if (ss > 0)
            ++cnt, v[cnt] = ss * vv, w[cnt] = ss * ww;
    }
    n = cnt;

    for (int i = 1; i <= n; i++)
        for (int j = m; j >= v[i]; j--)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
            
    cout << dp[m] << endl;
}