动态规划 4、基础背包问题总结(从01开始)「建议收藏」

动态规划 4、基础背包问题总结(从01开始)「建议收藏」一、01背包问题简述:n种物品,每种一个,选或不选随你,背包一定有容量,求不超过容量的情况下,价值最大。递归方程:dp[i][v]=max{dp[i][v],dp[i-1][v-c[i]]+w[i]}

大家好,又见面了,我是你们的朋友全栈君。

一、01背包问题

简述:n种物品,每种一个,选或不选随你,背包一定有容量,求不超过容量的情况下,价值最大。

递归方程:dp[i][v]=max{dp[i][v],dp[i-1][v-c[i]]+w[i]}

我们要注意的是下一次背包放I个物品的状态的可达性必然要满足上一次放I-1个物品时的可达性,觉得数学归纳法可以证明出来。所以这里有个隐含的判断,就是初始时memset(dp,0,sizeof(dp));在这里已经将dp清零,所以我们可以认为在dp==0是,这一节点是没有被访问到的。因为我们取得是大的值,自然0的情况怎么都不会被选中。

递推表示

memset(dp,0,sizeof(dp));

for(int i=1;i<=n;i++)
for(int j=m;j>=c[i];j--)//注意循环下标
dp[i][[j]=max(dp[i][j],dp[i-1][j-c[i]]+w[i]);

//cout<<dp[n][m];//我们可以判断出:即使在m-1时已经装满,但是m最满足不能装更多东西的时候时,dp[n][m]是同值的

 变式求值

我们可以组合这几个关键字:恰好装满、装载量不限定、价值最大、价值最小

1、价值最小,装载量不限定

解释:第一种可能是来酱油的,哈哈,我们什么都不装不就可以了。但是,我想在这里说明一个问题,那就是容量是一个限制条件,而不是决定最优解的条件,不要本末倒置了。

2、价值最大,装载量不限定

3、价值最大,恰好装满

解释:参考《背包九讲》

我们需要处理的是它的初始化部分

#define INF -0x3f3f3f3f
........
memset(dp,INF,sizeof(dp));
dp[0]=0;

 为什么要这样呢?开始我是不明白的。(现在还是不怎么理解,有木有!!!!)

看看大神的抽象解释:

为什么呢?可以这样理解:初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满,那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”,其它容量的背包均没有合法的解,属于未定义的状态,它们的值就都应该是-∞了。如果背包并非必须被装满,那么任何容量的背包都有一个合法解“什么都不装”,这个解的价值为0,所以初始时状态的值也就全部为0了。

4、价值最小,正好装满。

只需要把INF改成0x3f3f3f3f就可以了。

 

5、资源条件仅有一个。

举个例子来说。比如,给出一个数列 -1 19 0 34 -132 84 -2………

通过选取部分数字求和,使和尽量接近一个数N,或判断是否能正好加起来是N

这道题放到平时,可能惯性思维是暴力+剪枝,可是它是一个变相的背包问题,有木有!!!~~~~~

其实就是性价比为1(价值和体积之比为1)的情况。。。。。

6、价值形式改变

相关题目

1、hdu2546 饭卡(上述第5种情况)

 

Description

电子科大本部食堂的饭卡有一种很诡异的设计,即在购买之前判断余额。如果购买一个商品之前,卡上的剩余金额大于或等于5元,就一定可以购买成功(即使购买后卡上余额为负),否则无法购买(即使金额足够)。所以大家都希望尽量使卡上的余额最少。

某天,食堂中有n种菜出售,每种菜可购买一次。已知每种菜的价格以及卡上的余额,问最少可使卡上的余额为多少。
 

 

Input

多组数据。对于每组数据:

第一行为正整数n,表示菜的数量。n<=1000。

第二行包括n个正整数,表示每种菜的价格。价格不超过50。

第三行包括一个正整数m,表示卡上的余额。m<=1000。

n=0表示数据结束。

 

 

Output

对于每组输入,输出一行,包含一个整数,表示卡上可能的最小余额。
 

 

Sample Input

1 50 5 10 1 2 3 2 1 1 2 3 2 1 50 0

 

 

Sample Output

-45 32
简要分析:在最后金额大于等于5元时,是可以买任意价格的东西的,也就是说我们可以把价格最大的东西最后买。具体的操作可以看下面的注释。

 

#include<iostream>
#include<string.h>
#define maxn 1000+5
using namespace std;
int dp[maxn];
int w[maxn];
int main(){
	int n;
	while(cin>>n && n){
		int max1=0,p=0;
		for(int i=1;i<=n;i++){
			cin>>w[i];
			if(max1<w[i]){
				max1=w[i];//价格最大的物品放在最后选择一定是最优的
				p=i;
			}
		}
		int m;
		cin>>m;
		memset(dp,0,sizeof(dp));
		dp[0]=1;//表示什么都不买的状态是可达的
		if (m<5) cout<<m<<endl;
		else{
		m=m-5;
		w[p]=m+1;//小技巧,使得怎么都不能选到这个物品
		
		for(int i=1;i<=n;i++){
			for(int j=m;j>=w[i];j--){
				if(dp[j-w[i]])dp[j]=1;//表示此状态可达
			}
	    }
	    int ma=0;
	    for(int i=m;i>=0;i--){
		    if(dp[i]) {ma=i;break;}
	    }
		cout<<((m-ma)+(5-max1))<<endl;
	    }
    }
    return 0;
}

2、hdu2602 Bone Collector(情况2)

Problem Description
Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave …

The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ?



动态规划 4、基础背包问题总结(从01开始)「建议收藏」
 


Input
The first line contain a integer T , the number of cases.

Followed by T cases , each case three lines , the first line contain two integer N , V, (N <= 1000 , V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.
 


Output
One integer per line representing the maximum of the total value (this number will be less than 2
31).
 


Sample Input
1 5 10 1 2 3 4 5 5 4 3 2 1

 


Sample Output
14

 
题目分析:典型的01背包问题,容量限定,求最大价值。
#include<iostream>
#include<string.h>
#define  maxn 1000+5
using namespace std;
long long dp[maxn];
int v[maxn];
int w[maxn];
int main(){
	int t;
	cin>>t;
	while(t--){
		int n,m;
		cin>>n;
		cin>>m;
		for(int i=1;i<=n;i++){
			cin>>v[i];
		}
		for(int i=1;i<=n;i++){
			cin>>w[i];
		}
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++){
			for(int j=m;j>=w[i];j--){
				dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
			}
		}
		cout<<dp[m]<<endl;
	}
	return 0;
}

 

3、hdu2955(情况2)

Problem Description
The aspiring Roy the Robber has seen a lot of American movies, and knows that the bad guys usually gets caught in the end, often because they become too greedy. He has decided to work in the lucrative business of bank robbery only for a short while, before retiring to a comfortable job at a university.


动态规划 4、基础背包问题总结(从01开始)「建议收藏」


For a few months now, Roy has been assessing the security of various banks and the amount of cash they hold. He wants to make a calculated risk, and grab as much money as possible.

His mother, Ola, has decided upon a tolerable probability of getting caught. She feels that he is safe enough if the banks he robs together give a probability less than this.

 
Input
The first line of input gives T, the number of cases. For each scenario, the first line of input gives a floating point number P, the probability Roy needs to be below, and an integer N, the number of banks he has plans for. Then follow N lines, where line j gives an integer Mj and a floating point number Pj .

Bank j contains Mj millions, and the probability of getting caught from robbing it is Pj .
 
Output
For each test case, output a line with the maximum number of millions he can expect to get while the probability of getting caught is less than the limit set.

Notes and Constraints

0 < T <= 100

0.0 <= P <= 1.0

0 < N <= 100

0 < Mj <= 100

0.0 <= Pj <= 1.0

A bank goes bankrupt if it is robbed, and you may assume that all probabilities are independent as the police have very low funds.

 
Sample Input
3
0.04 3
1 0.02
2 0.03
3 0.05
0.06 3
2 0.03
2 0.03
3 0.05
0.10 3
1 0.03
2 0.02
3 0.05

 
Sample Output
2 4 6
 
#include<iostream>
#include<string.h>
#define maxn 10000+5
#define esp 0.0000001
using namespace std;
double dp[maxn];
double p[100+5];
int c[100+5];
int main(){
	int t;
	cin>>t;
	while(t--){
		int n;
		double mp;
		cin>>mp>>n;
		mp=1-mp;
		int mc=0;
		for(int i=1;i<=n;i++){
			cin>>c[i]>>p[i];
			mc=mc+c[i];
			p[i]=1-p[i];
		}		
		memset(dp,0,sizeof(dp));
		dp[0]=1;//什么都没有偷,逃跑概率是1
		for(int i=1;i<=n;i++){
			for(int j=mc;j>=c[i];j--)
			    if (dp[j-c[i]]>0){//表示这种状态是可达的
			      	dp[j]=max(dp[j],dp[j-c[i]]*p[i]);//偷盗当前数量的钱后,最优的解肯定是逃跑概率最小的时候
  			    }
		}
		int i;
		for(i=mc;i>=0;i--){
			if(dp[i]-mp>esp) break;//只要逃跑概率大于mp,那么这些状态都是可达的。
		}
		cout<<i<<endl;
	}
	return  0;
}

 

 

 

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/155073.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Python学习(九)Python缩进规则[通俗易懂]

    Python学习(九)Python缩进规则[通俗易懂]其它程序设计语言(如Java、C语言)采用大括号“{}”分隔代码块不同,Python采用代码缩进和冒号(:)来区分代码块之间的层次。在Python中,对于类定义、函数定义、流程控制语句、异常处理语句等,行尾的冒号和下一行的缩进,表示下一个代码块的开始,而缩进的结束则表示此代码块的结束。注意,Python中实现对代码的缩进,可以使用空格或者Tab键实现。但无论是手动敲空格,还…

    2022年10月13日
  • java编程_郑州java编程入门培训「建议收藏」

    java编程_郑州java编程入门培训「建议收藏」郑州java培训机构如何选择? 在选择java培训机构之前,必须进行大量的比较,然后才能决定去哪家培训机构。而现在千锋教育的Java实验班可以帮测试你是否适合学习Java。你可以找个机会去看看。要想学好java,就必须选择好的java培训机构,千锋的教育很好。口碑很重要,好的口碑是学生的真实的评价,这样的学校很靠谱。好的it培训学校有很好的老师指导学生学习,好的老师是学生学习路上的灯塔。选择…

  • pycharm怎么配置tensorflow环境_pycharm环境搭建

    pycharm怎么配置tensorflow环境_pycharm环境搭建Pycharm安装并搭建Tensorflow开发环境下载并安装pycharm1.下载2.pycharm配置python环境安装tensorflow1.输入清华仓库镜像2.创建tensorflow环境3.启动tensorflow环境4.安装cpu版本的TensorFlow5.测试TensorFlowPycharm中配置TensorFlow环境在操作之前先安装好python环境,我是安装的Anaconda,Anaconda下载安装教程可参考:https://blog.csdn.net/Chen_Meng_

  • MySQL——事务(Transaction)详解

    MySQL——事务(Transaction)详解该博客详解MySQL中的事务一、事务定义Transaction事务:一个最小的不可再分的工作单元;通常一个事务对应一个完整的业务(例如银行账户转账业务,该业务就是一个最小的工作单元)一个完整的业务需要批量的DML(insert、update、delete)语句共同联合完成事务只和DML语句有关,或者说DML语句才有事务。这个和业务逻辑有关,业务逻辑不同,DML语句的个数不同…

  • LAN8720A网络模块关于时钟的使用问题「建议收藏」

    LAN8720A网络模块关于时钟的使用问题「建议收藏」微雪的LAN8720A驱动电路:正点原子LAN8720A驱动电路:1、nINTSELConfiguration从原理图中可以看出正点原子的LAN8720A模块所使用的晶振是25M,而微雪的LAN8720A模块使用的晶振是50M,根据数据手册和结合原理图可以看出,微雪的LAN8720A的nINTSEL没有接下拉,则是默认使用内部上拉到高电平,即nINTSEL=1,为REF_CLKInMode模式,所以选用50M的晶振。…

  • java使用httpclient调用第三方接口

    java使用httpclient调用第三方接口java使用httpclient调用第三方接口HttpClientUtil工具类packagecom.fz.util;importjava.io.File;importjava.net.URL;importjava.util.ArrayList;importjava.util.List;importjava.util.Map;importorg.apache.ht…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号