Java教程

分组背包问题

本文主要是介绍分组背包问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

分组背包问题

  1. 问题描述:

    有 N 组物品和一个容量是 V 的背包。

    每组物品有若干个,同一组内的物品最多只能选一个。
    每件物品的体积是 vij,价值是 wij,其中 i 是组号,j 是组内编号。

    求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。

  2. 分析:

    f[i][j]表示只看前i的情况下,背包中物品最大体积为j时背包最大价值;

    跟0 ~ 1背包问题思路差不多,无非是多了一层组内循环来求组内最大价值。

  3. 示例代码:

    #include <bits/stdc++.h>
    using namespace std;
    
    const int N = 105;
    int n, m;
    int s[N], v[N][N], w[N][N], f[N];
    
    int main(){
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i ++){
            scanf("%d",s + i);
            for(int j = 1; j <= s[i]; j ++){
                scanf("%d%d", v[i] + j, w[i] + j); 
            }
        }
    
        for(int i = 1; i <= n; i ++)
            for(int j = m; j >= 0; j --)
                for(int k = 1; k <= s[i]; k ++)
                    if(v[i][k] <= j)
                        f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
        printf("%d", f[m]);
        return 0;
    }
    
这篇关于分组背包问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!