免费p站推广网站入口_企业营销的目的_企业管理培训视频免费_快速建站哪个平台好

一、定义

完全背包可以看作是01背包演变过来的，其定义如下：
我们有一个背包容量是V，给定我们N种物品，每个物品有其对应的价值wi和占用体积vi（ $1\leq i \leq N$ ）,并且每种物品都有无限个，要求我们在不超过V的情况下，选取物品，使得总价值最大化。
它和01背包唯一的区别就是在物品的选择次数上。完全背包中，每种物品是由无限个的，你可以选择任意多个物品，当然选0个也是可以的，而后者只能选或者不选。

二、模板题

完全背包问题描述

有一个容量为 ( V = 10 ) 的背包，现有 ( N = 4 ) 种不同的物品，每种物品的数量是无限的。每种物品的重量和价值如下：

物品 1：重量为 2，价值为 3
物品 2：重量为 3，价值为 4
物品 3：重量为 4，价值为 5
物品 4：重量为 5，价值为 6

你可以选择任意数量的每种物品，但总重量不能超过背包的容量 ( V = 10 )。你的目标是在不超过背包容量的前提下，选取物品，使得背包内物品的总价值最大化。

请编写程序，求出背包能获得的最大价值。

输入：

背包的总容量 ( V = 10 )
物品的重量数组：weights = {2, 3, 4, 5}
物品的价值数组：values = {3, 4, 5, 6}

输出：

背包能获得的最大价值：12

示例：

输入:
背包容量: 10
物品重量: [2, 3, 4, 5]
物品价值: [3, 4, 5, 6]返回:
背包能获得的最大价值为: 12

解题思路：

class CompleteKnapsack {/*** 解决完全背包问题* @param V 背包的总容量* @param weights 物品的容量数组* @param values 物品的价值数组* @return 背包能获得的最大价值*///这个函数用来返回最大价值，在不超过V的情况下。public static int solve(int V, int[] weights, int[] values) {}
}

1. 状态表示：

//dp[v]表示，背包容量为v时，获取的最大价值
int[] dp=new int[V+1];

2. 状态转移方程
当前第i个物品的价值是vlues[i]，体积是weigths[i]，如何求dp[i]呢？
dp[v]表示：背包容量为v时，获取的最大价值。因此我们需要将当前的容量v和第i个物品的体积weigths[i]进行比较：

  	//在背包容量v不小于第i个物品的体积的情况下，尝试把第i个物品放进包里if (weights[i] <=v) {              dp[v] = Math.max(dp[v], dp[v - weights[i]] + values[i]);}//weights[i]>v不做任何处理，因为第i个物品体积太大了，即使容量为v的背包没有装任何东西，也装不下这个物品

3.初始化
根据状态表示，我们只需要确保dp[0]为正确的值即可。dp[0]表示背包容量为0时，获取的最大价值。因为根本装不了东西自然dp[0]=0

4. 填表顺序

因为完全背包是可以无限选择多个同种物品的，只要不超过背包容量，所以我们先从1到V枚举所有可能的背包容量，然后再内层循环从1到N枚举所有的物品，这样才能确保有多次选择同一个物品的可能：

int N=weights.length; // 物品的数量for (int v = 0; v <=V; v++) for (int i = 0; i <N; i++) {// 遍历所有的物品//在背包容量v不小于第i个物品的体积的情况下，尝试把第i个物品放进包里if (weights[i] <=v)              dp[v] = Math.max(dp[v], dp[v - weights[i]] + values[i]);                }

5. 确定返回值
即，dp[V]（容量为V的背包，获取的最大价值）

代码模板（Java）

class CompleteKnapsack {/*** 解决完全背包问题* @param V 背包的总容量* @param weights 物品的容量数组* @param values 物品的价值数组* @return 背包能获得的最大价值*/public static int solve(int V, int[] weights, int[] values) {int N = weights.length; // 物品的数量int[] dp = new int[V + 1]; // dp[v]表示容量为i的背包所能装入的最大价值// 遍历所有可能的背包容量for (int v = 0; v <=V; v++) {// 遍历所有的物品for (int i = 0; i <N; i++) {//在背包容量v不小于第i个物品的体积的情况下，尝试把第i个物品放进包里if (weights[i] <=v) {// 比较不放入该物品和放入该物品的情况，取较大值// dp[v]：不放入当前物品时的最大价值// dp[v - weights[i]] + values[i]：放入当前物品后的最大价值dp[v] = Math.max(dp[v], dp[v - weights[i]] + values[i]);}}}// 返回背包容量为V时能获得的最大价值return dp[V];}

三、实战题

1、题目

蓝桥云课题目链接
在这里插入图片描述

2、解题思路

先入为主，大家想到的肯定是用完全背包去做，当然也的确如此，不过需要一点转化。首先这个电影是可以选择重复上映多次的，这个一定要清楚，题目中并没有明确说明。这满足完全背包无限选取同一个物品的特征。（第i部电影的放映时长就是i物品的体积，第i部电影的利润就是i物品的价值）
另外，题目中每场电影上映完至少要等待K分钟才可以上映下一场电影，这就比较的难受。有没有什么办法可以避开它呢？
当然有，而且思路并不难：直接把时间间隔K视为每一个物品的体积的一部分（每部电影时长增加K）。值得注意的是，最后上映的一部电影是不需要增加休息时间的间隔K的，因为后面已经没有电影要放了，所以我们要对最后一个位置做特殊处理：
也不用把它想得太难，直接扩容背包的最大体积即可，也就是电影院的放映总时间增加 K即可。
通过上面的转化，题目就变成了经典的完全背包问题了。

背包的容量： 电影的总放映时间+K
物品的体积： 第i部电影的放映时长+K
物品的价值： 第i部电影的利润
物品的数量： 可放映的电影的数量

3、AC_Code_Java

import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {//转化成完全背包（体积有限，但是同一个物品可以无限拿多个）//所以我们直接对每个电影的时间都加上一个间隔//但是由于最后一个电影不需要间隔，所以可以在最大时间M后面+kpublic static void main(String[] args){Scanner sc=new Scanner(System.in);int m=sc.nextInt();//开店时间int n=sc.nextInt();//电影的多少int[] t=new int[n+1];//每部电影的放映时长int[] p=new int[n+1];//每部电影的利润for(int i=1;i<=n;i++){t[i]=sc.nextInt();p[i]=sc.nextInt();}int k=sc.nextInt();//最小间隔//把物品的体积统一for(int i=1;i<=n;i++)t[i]+=k;//电影院的总放映时长加上时间间隔，处理最后一个特殊情况m+=k;//dp[i]电影院总放映时长为i时，最大利润int[] dp=new int[m+1];for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(i>=t[j])dp[i]=Math.max(dp[i],dp[i-t[j]]+p[j]);}}System.out.print(dp[m]);}
}