63、背包问题

2024-06-06 09:36
文章标签 问题 背包 63

本文主要是介绍63、背包问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

背包问题

题目描述

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi,价值是 wi。

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

输入格式

第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。

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

输出格式

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

数据范围

  • 0 < N , V ≤ 1000 0 < N,V ≤ 1000 0<N,V1000
  • 0 < v i , w i ≤ 1000 0<vi,wi≤1000 0<vi,wi1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例:
8

Solution

思路

  • 状态:dp[i][j]表示只看前i个物品,总体积不超过j的情况下,背包中物品的最大价值

    最后答案就是dp[N][V]

  • 状态转移:找最后一个不同点,也就是选最后一个物品的不同方案。对于dp[i][j]有两种情况:

    1. 不选择当前的第件物品/第i件物品比背包容量要大

      dp[i][j] = dp[i-1][j]

    2. 选择当前的第i件物品(潜在要求第i件物品体积小于等于背包总容量,即v[i] >= j

      dp[i][j] = dp[i-1][j-v[i]] + w[i]

    上面两种情况取max作为当前的最优解。

  • 边界:dp[0][0] = 0

  • 注意一些细节:

    1. 如果j表示体积正好是j的话,那么答案就需要遍历求max。如果表示的是 不超过j的话,答案就是dp[N][V]
    2. 如果题目要求背包必须放满,那么 dp[0] [0…V] 中仅仅有 dp[0][0] 为0,其余值需被设置为-INF,返回dp[V]。
    3. 如果并没有要求必须把背包装满,而是只希望总价值尽量大,初始化时应该将dp[0...V ]全部设为0, 返回dp[V]。
    4. ij从1开始循环。

普通版

import java.util.*;class Main{public static void main(String[] args){// 输入数据Scanner scan = new Scanner(System.in);int N = scan.nextInt();int V = scan.nextInt();int[] v = new int[N + 10];int[] w = new int[N + 10];for(int i = 1; i <= N; i++){v[i] = scan.nextInt();w[i] = scan.nextInt();}scan.close();// 开始dpint[][] dp = new int[N + 10][V + 10];for(int i = 1; i <= N; i++){for(int j = 1; j <= V; j++){// 放进去和不放进去取最大值dp[i][j] = dp[i - 1][j];if(j >= v[i])dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);}}// int res = 0;// for(int i = 0; i <= V; i++) res = Math.max(res, dp[N][i]);// System.out.println(res);// 或者System.out.println(dp[N][V]);}
}

进阶版

  1. dp[j]表示体积不超过j的情况下的最大价值。
  2. dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]),看j,第二维要不就是用j,要不是就是用比j小的数。
  3. 如果j从小往大循环,后面的dp[j]可能已经被前面的更新了,相当于dp[i][j - v[i]]
  4. 所以让j从大到小循环。把第一维去掉,变成了dp[j] = max(dp[j], dp[j-v[i] + w[i]),比如计算第二层的时候,dp[j-v[i]]还没有在第二层被更新过(因为j-v[i]j小),所以这个时候的dp[j-v[i]]存的是上一层的状态,也就是dp[i-1][j-v[i]]
import java.util.*;class Main{public static void main(String[] args){// 输入数据Scanner scan = new Scanner(System.in);int N = scan.nextInt();int V = scan.nextInt();int[] v = new int[N + 10];int[] w = new int[N + 10];for(int i = 1; i <= N; i++){v[i] = scan.nextInt();w[i] = scan.nextInt();}scan.close();// 开始dpint[] dp = new int[V + 10];for(int i = 1; i <= N; i++){for(int j = V; j >= v[i]; j--){// 放进去和不放进去取最大值dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);}}// 如果初始化:dp[0]为0,其他为负无穷,就要遍历取最大值。// 这种情况对应体积恰好为V的价值,保证所有的状态从0转移来//// 如果初始化:dp[i]都为0,dp[V]也是最大值。假设dp[k]为最大值。// dp[k]从0转移过来,那dp[V]从dp[V-k]转移过来,是一样的System.out.println(dp[V]);}
}

这篇关于63、背包问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1035733

相关文章

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

poj2576(二维背包)

题意:n个人分成两组,两组人数只差小于1 , 并且体重只差最小 对于人数要求恰好装满,对于体重要求尽量多,一开始没做出来,看了下解题,按照自己的感觉写,然后a了 状态转移方程:dp[i][j] = max(dp[i][j],dp[i-1][j-c[k]]+c[k]);其中i表示人数,j表示背包容量,k表示输入的体重的 代码如下: #include<iostream>#include<

hdu2159(二维背包)

这是我的第一道二维背包题,没想到自己一下子就A了,但是代码写的比较乱,下面的代码是我有重新修改的 状态转移:dp[i][j] = max(dp[i][j], dp[i-1][j-c[z]]+v[z]); 其中dp[i][j]表示,打了i个怪物,消耗j的耐力值,所得到的最大经验值 代码如下: #include<iostream>#include<algorithm>#include<

csu(背包的变形题)

题目链接 这是一道背包的变形题目。好题呀 题意:给n个怪物,m个人,每个人的魔法消耗和魔法伤害不同,求打死所有怪物所需的魔法 #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>//#include<u>#include<map

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu1171(母函数或多重背包)

题意:把物品分成两份,使得价值最接近 可以用背包,或者是母函数来解,母函数(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v) 其中指数为价值,每一项的数目为(该物品数+1)个 代码如下: #include<iostream>#include<algorithm>

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库,瞬间耗尽数据库资源,导致数据库无法使用。 解决方案: 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内,大量缓存数据同时失效,导致所有请求直接涌向数据库,瞬间增加数据库的负载压力,可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k