完全背包 订阅
完全背包,是一种经典的信息学问题,是研究一个固定容量的背包内能装多大价值的东西的问题。 展开全文
完全背包,是一种经典的信息学问题,是研究一个固定容量的背包内能装多大价值的东西的问题。
信息
属    于
一种经典的信息学问题
概    念
研究固定容量背包能装多大价值
类似于
01背包问题
中文名
完全背包
完全背包完全背包问题
题目有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的体积是c,价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量,且价值总和最大。
收起全文
精华内容
下载资源
问答
  • 完全背包

    2021-01-22 22:57:10
    Dynamic Programming之完全背包 01背包与完全背包的比较: 在0/1背包问题中,第 i 件物品只可以放0个或者1个,即选择或者不选。而在完全背包问题中,第 i 件物品可以放入0,1,2…个。即每件物品可以放入无限多次。 ...

    Dynamic Programming之完全背包

    01背包与完全背包的比较:

    在0/1背包问题中,第 i 件物品只可以放0个或者1个,即选择或者不选。而在完全背包问题中,第 i 件物品可以放入0,1,2…个。即每件物品可以放入无限多次。

    与0/1背包相同的是,最大价值是物品数量 i 与背包容量 j 的函数。最终的最大价值就是物品数量 i 从0增长到n,背包容量 j 从0增长到m时的 f [ n ] [ m ] 函数值。f[ i ][ j ]表示前 i 件物品放入容量为 j 的背包的最大价值。

    ①若当前物品的重量大于背包的容量,即 w[ i ] > j 。则该物品不能放入 。f [ i ][ j ] 更新为 f [ i - 1] [ j ]。
    ②若当前物品的重量小于背包的容量,即 w[ i ] < j 。则第 i 件物品可以放入背包,但需要考虑代价,故分放入和不放入两种情况。
    (1)第 i 件物品不放入背包。f [ i ][ j ] = f [ i - 1] [ j ]
    (2)第 i 件物品放入背包。f[ i ][ j ] = f[ i ][ j - w [ i ] ] + price[ i ]

    完全背包的状态转移方程

    在这里插入图片描述
    例题

    原题链接

    有 N 种物品和一个容量是 V 的背包,每种物品都有无限件可用。
    第 i 种物品的体积是 vi,价值是 wi。
    求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出最大价值。

    输入格式

    第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i
    种物品的体积和价值。

    输出格式

    输出一个整数,表示最大价值。

    数据范围

    0 < N,V ≤ 1000
    0 < vi,wi ≤ 1000

    输入样例

    4 5
    1 2
    2 4
    3 4
    4 5

    输出样例:

    10

    AC代码

    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 1010;
    int f[N][N];//二维数组
    int v[N];//价值数组
    int w[N];//重量数组
    
    int main(){
        int n,m;
        scanf("%d%d",&n,&m);
        
        //初始化重量和价值数组
        for (int i = 1;i <= n;i++) scanf("%d%d",&w[i],&v[i]);
        
        //用i遍历物品,用j遍历背包的容量
        for (int i = 1;i <= n;i++){
            for (int j = 1;j <= m;j++){
                //状态转移方程
                if (j < w[i]) f[i][j] = f[i - 1][j];
                else f[i][j] = max(f[i - 1][j],f[i][j - w[i]] + v[i]);
            }
        }
        
        printf("%d\n",f[n][m]);
    }
    

    比较0/1和完全背包状态转移方程

    • 0/1背包
    for (int i = 1;i <= n;i++)
            for (int j = m;j >= 1;j--)//j:注意要从后往前枚举(逆推)
                if (j >= w[i]) dp[j] = max(dp[j],dp[j - w[i]] + v[i]);//放得下
    
    
    • 完全背包
    for (int i = 1;i <= n;i++)
            for (int j = 1;j <= m;j++)//j:注意要从前往后枚举(顺推)
                if (j >= w[i]) dp[j] = max(dp[j],dp[j - w[i]] + v[i]);//放得下
    
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,230
精华内容 4,492
关键字:

完全背包