文档章节

背包问题总结

GenHao2
 GenHao2
发布于 02/07 20:12
字数 4719
阅读 19
收藏 1

01背包

不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些道具,于是他来到了地精商店前.

死亡骑士:"我要买道具!"

地精商人:"我们这里有三种道具,血瓶150块一个,魔法药200块一个,无敌药水350块一个."

死亡骑士:"好的,给我一个血瓶."

说完他掏出那张N元的大钞递给地精商人.

地精商人:"我忘了提醒你了,我们这里没有找客人钱的习惯的,多的钱我们都当小费收了的,嘿嘿."

死亡骑士:"......你妹"

死亡骑士想,与其把钱当小费送个他还不如自己多买一点道具,反正以后都要买的,早点买了放在家里也好,但是要尽量少让他赚小费.


现在死亡骑士希望你能帮他计算一下,最少他要给地精商人多少小费.

上面就是一个01背包问题。上面的问题可以描述为:

有n个物品,每个物品的重量为weight[i],每个物品的价值为value[i]。现在有一个背包,它所能容纳的重量为total,问:当你面对这么多有价值的物品时,你的背包所能带走的最大价值是多少?


思路:每个物品无非是装入背包或者不装入背包,那么就一个一个物品陆续放入背包中。可以有

tab[i][j] = max(tab[i-1][j-weight[i]]+value[i],tab[i-1][j]) ({i,j|0<i<=n,0<=j<=total})

其中i表示放第i个物品,j表示背包所容纳的重量,那么tab[i-1][j-weight[i]]+value[i]表示放入第i物品,刚开始接触会有疑问,tab[i-1][j-weight[i]]这个值,可以这样理解:tab[i-1][j]为装到上一个物品在背包j容量时的最佳值,那么如果我要求在j容量的时候放入现在的i物品的价值,那么是不是要先得到容量为(j-weight[i])时候的价值,即先得到 tab[i-1][j-weight[i]] ,所以 tab[i-1][j-weight[i]]+value[i] 为放入第i物品的价值; tab[i-1][j] 就是不放入第i个物品。

动态规划的思维就在这里体现了,即tab[i-1][j]是tab[i][j]的最优解(我觉得上面的思路讲解较容易理解)。

例子:5个物品,(重量,价值)分别为:(5,12),(4,3),(7,10),(2,3),(6,6)。

故有:

for i=[0,n)
    for(j=totle;j>=weight[i]; j--)
        tab[j] = max(tab[j-weight[i]]+value[i],tab[j])
 /* print tab[0][total] */


 完全背包


不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些道具,于是他来到了地精商店前.


死亡骑士:"我要买道具!"


地精商人:"我们这里有三种道具,血瓶150块无限个,魔法药200块无限个,无敌药水350块无限个."


死亡骑士:"好的,给我一个血瓶."


说完他掏出那张N元的大钞递给地精商人.


地精商人:"我忘了提醒你了,我们这里没有找客人钱的习惯的,多的钱我们都当小费收了的,嘿嘿."


死亡骑士:"......你妹"


死亡骑士想,与其把钱当小费送个他还不如自己多买一点道具,反正以后都要买的,早点买了放在家里也好,但是要尽量少让他赚小费.


现在死亡骑士希望你能帮他计算一下,最少他要给地精商人多少小费.


上面的魔兽场景描述跟上面的只有小小的差异,就是物品有一个变为了无限个,这就是完全背包问题。完全背包问题可以描述为:


有n种物品,每种物品有无限个,每个物品的重量为weight[i],每个物品的价值为value[i]。现在有一个背包,它所能容纳的重量为total,问:当你面对这么多有价值的物品时,你的背包所能带走的最大价值是多少?

有了上面01背包的式子,这题会变的容易理解很多,只是这个式子要有小小的改动。01背包在二维数组上操作,就是为了防止一个物品被放入多次的情况。因此一维数组可以满足完全背包的问题。如下:

tab[j] = max(tab[j-weight[i]]+value[i],tab[j]);({i,j|0<i<=n,0<=j<=total})

根本就是一样的,只不过物品可以被放多次。


故有:

for i=[0,n)
    for(j=weight[i]; j<=total; j++)
        tab[j] = max(tab[j-weight[i]]+value[i],tab[j])
/*    print tab[0][total]    */

 

 多重背包


不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些道具,于是他来到了地精商店前.


死亡骑士:"我要买道具!"


地精商人:"我们这里有三种道具,血瓶150块a个,魔法药200块b个,无敌药水350块c个."


死亡骑士:"好的,给我一个血瓶."


说完他掏出那张N元的大钞递给地精商人.


地精商人:"我忘了提醒你了,我们这里没有找客人钱的习惯的,多的钱我们都当小费收了的,嘿嘿."


死亡骑士:"......你妹"


死亡骑士想,与其把钱当小费送个他还不如自己多买一点道具,反正以后都要买的,早点买了放在家里也好,但是要尽量少让他赚小费.


现在死亡骑士希望你能帮他计算一下,最少他要给地精商人多少小费.


上面的魔兽场景描述跟上面的又有了小小的差异,就是物品有一个变为了有限个,问题也就变成了多重背包问题。

 

有n种物品,每种物品有amount[i]个,每个物品的重量为weight[i],每个物品的价值为value[i]。现在有一个背包,它所能容纳的重量为total,问:当你面对这么多有价值的物品时,你的背包所能带走的最大价值是多少?

多重和完全更接近,多了数量的限制,用一个count[n]计数数组来限制物品i的数量。当放入第i个物品是较优值的时候,count[i]=count[j-weight[i]]+1(j 的含义请查看代码);这样做是因为,放入第i个物品的操作是基于count[j-weight[i]]放入的,所以当count[i-weight[i]]>=amount[i]时,就要阻止放入即便放入第i个物品是较优值。 故有:

for i=[0,n)
    /*    将count数组清零        */
    for(j=weight[i]; j<=total; j++)
        if    count[j-weight[i]]<amout[i]
            tab[j] = max(tab[j-weight[i]]+value[i],tab[j]);
            if    tab[j]=tab[j-weight[i]]+value[i]   //    决定放入i是较优解
                count[i] = count[j-weight[i]] + 1
        else    if    tab[j]=0       //    防止装第1个物品和装其他物品的情况
            tab[j] = tab[j-1],count[j] = count[j-1]
        else    count[j] = count[j-1]
/*    print tab[0][total]    */

 相关例题

HDU2546:饭卡
http://acm.hdu.edu.cn/showproblem.php?pid=2546(01背包)
要注意的是这里只要剩余的钱不低于5元,就可以购买任何一件物品,所以5在这道题中是很特许的,

再使用01背包之前,我们首先要在现在所拥有的余额中保留5元,用这五元去购买最贵的物品,

而剩下的钱就是背包的总容量,可以随意使用

#include <stdio.h>
#include <algorithm>
using namespace std;
int main()
{
    int n;
    while(~scanf("%d",&n),n)
    {
        int i,price[2013]= {0},dp[2013] = {0};
        for(i = 1; i<=n; i++)
            scanf("%d",&price[i]);
        sort(price+1,price+1+n);
        int MAX=price[n];
        int j,m;
        scanf("%d",&m);
        if(m<5)//低于5元不能购买
        {
            printf("%d\n",m);
            continue;
        }
        m-=5;//取出5元用于购买最贵的物品
        for(i = 1; i<n; i++)//01背包
        {
            for(j = m;j>=price[i];j--)
            {
                dp[j] = max(dp[j],dp[j-price[i]]+price[i]);
            }
        }
        printf("%d\n",m+5-dp[m]-MAX);
    }
    return 0;
}

 

HDU 4508湫湫系列故事——减肥记I

http://acm.hdu.edu.cn/showproblem.php?pid=4508(完全背包)

#include<iostream>
#include<algorithm>
using namespace std;
int max(int a,int b)
{
	if(a>b) return a;
    else    return b;
}
int main()
{
	int n,m;
	int a[100005],b[100005],c[100005];
	while(scanf("%d",&n)!=EOF)
	{
		memset(c,0,sizeof(c));
		for(int i=0;i<n;i++)
			scanf("%d%d",&a[i],&b[i]);
		scanf("%d",&m);
		for(int j=0;j<n;j++)
		{
			for(int k=b[j];k<=m;k++)
			{
				c[k]=max(c[k-b[j]]+a[j],c[k]);
			}
		}
		printf("%d\n",c[m]);
	}
	return 0;
}

 

hdu 2602 Bone Collector

http://acm.hdu.edu.cn/showproblem.php?pid=2602(01背包)

注意和上题进行比较。

#include<iostream>
#include<algorithm>
using namespace std;
int max(int a,int b)
{
	if(a>b) return a;
    else    return b;
}
int main()
{
	int T,N,V;
	int i,j,k;
	int v[1005],w[1005],c[1005];
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&N,&V);
		for(i=0;i<N;i++)
			scanf("%d",&v[i]);
		for(i=0;i<N;i++)
			scanf("%d",&w[i]);
		memset(c,0,sizeof(c));
		for(i=0;i<N;i++)
		{
			for(j=V;j>=w[i];j--)
			{
				c[j]=max(c[j],c[j-w[i]]+v[i]);
			}
		}
		printf("%d\n",c[V]);
	}
	return 0;
}

相关链接点击打开链接
 

HDU 1203I NEED A OFFER!

#include <iostream>
#include<algorithm>
using namespace std;
const int N=10000+1;
int a[N];
float b[N],f[N]; 
int main(int argc, char *argv[])
{
    int n,m;
	while(scanf("%d%d",&n,&m)!=EOF&&m+n)
	{
		memset(f,0,sizeof(f));
		for(int i=0;i<m;i++) 
			cin>>a[i]>>b[i];
		for(int i=1;i<m;i++)
		{
			for(int j=n;j>a[i];j--)
			{
				f[j]=max(f[j],1-(1-f[j-a[i]])*(1-b[i]));
			}
		}
		printf("%.1f%%\n",f[n]*100); 
	} 
	return 0;
}
//01背包问题
问题大意:同学a要出国留学,他有n万元的存款,可以向m所学校申请,每所学校的费用c[i],录取他的可能性w[i],
根据n的数量,他可以同时向s所大学同时申请,假设共有q种申请方式,现在求q种方式中他被录取的最大的可能性是多少。
求前i所大学录取他的的最大可能性
假设他同时向两所学校申请,录取概率分别为a,b
他没被录取的概率是(1-a)*(1-b)
那么他被录取的概率是1-(1-a)*(1-b)
f[j] = max{f[j],1-(1-f[j-c[i]])*(1-w[i])}
max中的f[j]表示分析完上一所学校之后j万元能够获取的最大被录取概率
如果等号左边的f[j]等于max中的f[j],就说明花费j万元时不向第i校申请,所以和第i-1校时的j万元所获取的最大被录取概率一样。
max中的(1-(1-f[j-c[i]])*(1-w[i]))表示选择了i校之后被录取的概率。
f[j-c[i]]:除去i校的申请费之后,用剩余的钱所获取的被录取最大概率。


HDU 1248寒冰王座

#include <stdio.h>
#include <string.h>
int max(int a,int b)
{
	return  a>b?a:b;
}
int main(int argc, char *argv[])
{
    int i,j,m,n;
	int dp[10001];
	int a[3]={150,200,350};
	scanf("%d",&n);
	while(n--)
	{
		scanf("%d",&m);
		memset(dp,0,sizeof(dp));
		for(i=0;i<3;i++)
		{
			for(j=a[i];j<=m;j++)
			{
				dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
			}    
		}
		printf("%d\n",m-dp[m]);
	}   
	return 0;
}
//完全背包问题


HDU 2602 Bone Collector

#include <iostream>
#include <cstring>
using namespace std;
int dp[1001], v[1000], p[1000];
inline int max(int a, int b) { return a>b?a:b;  }
int main()
{ int c;
scanf("%d", &c);
while (c--) {
	int n, V, i, j;
	scanf("%d %d", &n, &V);
	for (i=0; i<n; i++)   
		scanf("%d", &p[i]);
	for (i=0; i<n; i++)  
		scanf("%d", &v[i]);
	memset(dp, 0, sizeof(dp));
	for (i=0; i<n; i++)
		for (j=V; j>=v[i]; j--)
			dp[j] = max(dp[j], dp[j-v[i]] + p[i]);
		printf("%d\n", dp[V]);
}
}
//01背包问题

 

首先我们把三种情况放在一起来看:

01背包(ZeroOnePack): 有N件物品和一个容量为V的背包。(每种物品均只有一件)第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

完全背包(CompletePack): 有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

多重背包(MultiplePack): 有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用,每件费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

比较三个题目,会发现不同点在于每种背包的数量,01背包是每种只有一件,完全背包是每种无限件,而多重背包是每种有限件。

——————————————————————————————————————————————————————————–:

01背包(ZeroOnePack): 有N件物品和一个容量为V的背包。(每种物品均只有一件)第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。

用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

把这个过程理解下:在前i件物品放进容量v的背包时,

它有两种情况:

第一种是第i件不放进去,这时所得价值为:f[i-1][v]

第二种是第i件放进去,这时所得价值为:f[i-1][v-c[i]]+w[i]

(第二种是什么意思?就是如果第i件放进去,那么在容量v-c[i]里就要放进前i-1件物品)

最后比较第一种与第二种所得价值的大小,哪种相对大,f[i][v]的值就是哪种。

(这是基础,要理解!)

这里是用二位数组存储的,可以把空间优化,用一位数组存储。

用f[0..v]表示,f[v]表示把前i件物品放入容量为v的背包里得到的价值。把i从1~n(n件)循环后,最后f[v]表示所求最大值。

*这里f[v]就相当于二位数组的f[i][v]。那么,如何得到f[i-1][v]和f[i-1][v-c[i]]+w[i]?(重点!思考)
首先要知道,我们是通过i从1到n的循环来依次表示前i件物品存入的状态。即:for i=1..N
现在思考如何能在是f[v]表示当前状态是容量为v的背包所得价值,而又使f[v]和f[v-c[i]]+w[i]标签前一状态的价值?

逆序!

这就是关键!

1for i=1..N
2   for v=V..0
3        f[v]=max{f[v],f[v-c[i]]+w[i]};
4

分析上面的代码:当内循环是逆序时,就可以保证后一个f[v]和f[v-c[i]]+w[i]是前一状态的!
这里给大家一组测试数据:

测试数据:
10,3
3,4
4,5
5,6

这个图表画得很好,借此来分析:

C[v]从物品i=1开始,循环到物品3,期间,每次逆序得到容量v在前i件物品时可以得到的最大值。(请在草稿纸上自己画一画)

这里以一道题目来具体看看:

题目:http://acm.hdu.edu.cn/showproblem.php?pid=2602

代码在这里:http://www.wutianqi.com/?p=533

分析:

 

具体根据上面的解释以及我给出的代码分析。这题很基础,看懂上面的知识应该就会做了。

——————————————————————————————————————————————————————————–

完全背包:

完全背包(CompletePack): 有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

完全背包按其思路仍然可以用一个二维数组来写出:

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}

同样可以转换成一维数组来表示:

伪代码如下:
 

for i=1..N
    for v=0..V
        f[v]=max{f[v],f[v-c[i]]+w[i]}


 

顺序!

想必大家看出了和01背包的区别,这里的内循环是顺序的,而01背包是逆序的。
现在关键的是考虑:为何完全背包可以这么写?
在次我们先来回忆下,01背包逆序的原因?是为了是max中的两项是前一状态值,这就对了。
那么这里,我们顺序写,这里的max中的两项当然就是当前状态的值了,为何?
因为每种背包都是无限的。当我们把i从1到N循环时,f[v]表示容量为v在前i种背包时所得的价值,这里我们要添加的不是前一个背包,而是当前背包。所以我们要考虑的当然是当前状态。
这里同样给大家一道题目:

题目:http://acm.hdu.edu.cn/showproblem.php?pid=1114

代码:http://www.wutianqi.com/?p=535

(分析代码也是学习算法的一种途径,有时并不一定要看算法分析,结合题目反而更容易理解。)

——————————————————————————————————————————————————————————–

多重背包

多重背包(MultiplePack): 有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用,每件费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可,因为对于第i种物品有n[i]+1种策略:取0件,取1件……取n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值,则有状态转移方程:

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}

这里同样转换为01背包:

普通的转换对于数量较多时,则可能会超时,可以转换成二进制(暂时不了解,所以先不讲)

对于普通的。就是多了一个中间的循环,把j=0~bag[i],表示把第i中背包从取0件枚举到取bag[i]件。

给出一个例题:

题目:http://acm.hdu.edu.cn/showproblem.php?pid=2191

代码:http://www.wutianqi.com/?p=537

 

 

 

 

© 著作权归作者所有

上一篇: Mybatis 基础知识
下一篇: SpringMVC 常用注解
GenHao2
粉丝 13
博文 201
码字总数 279463
作品 0
马鞍山
程序员
私信 提问
解决最优子结构问题的两种方法----动态规划和贪心算法

1、两种重要算法思想: 动态规划,贪心算法 2、动态规划: 基本原理:动态规划英文名dynamic programming。其中pogramming指的是表格法,而非编写计算机程序。因此,可以初步得出动态规划的基...

thoresa
2015/05/18
0
0
前端与算法-动态规划之01背包问题浅析与实现

去年因为工作中的某个应用场景,需要使用到动态规划,为此花了些时间啃了啃背包算法 为啥去年的东西,今年才写粗来,也许大概是懒吧 动态规划 Dynamic Programming 先简单说下什么是动态规划...

小黎也
07/31
0
0
总结——01背包问题 (动态规划算法)

0-1 背包问题:给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值为 vi 。 问:应该如何选择装入背包的物品,使得装入背包中的物品的总价值最大? 分析一波,面对每个物品,我...

xp731574722
2017/04/25
0
0
子集合加总问题(Subset sum problem)

两年前在做一个ERP项目时,有个客户提出,根据订单给出的每个货品的数量(库里存的有每个货品最小包装的重量,体积和长宽高),输入包装箱的承重和体积和长宽高,然后我需要你们提供一个包装...

TOTOTO_TOTO
2013/12/15
0
0
动态规划 &

一、 动态规划(Dp问题):解决问题的关键点 1) 递推公式:(最有子结构) 2) 数据的初始化 用例分析: a. 01 背包的问题(Knapsack Problem) 定义: 一个背包的容量V; 存在N个物品:w[i...

Playboy002
2015/07/17
42
0

没有更多内容

加载失败,请刷新页面

加载更多

不可不说的Java“锁”事

前言 Java提供了种类丰富的锁,每种锁因其特性的不同,在适当的场景下能够展现出非常高的效率。本文旨在对锁相关源码(本文中的源码来自JDK 8)、使用场景进行举例,为读者介绍主流锁的知识点...

美团技术团队
6分钟前
1
0
ali oss util demo

package com.example.demo;import com.aliyun.oss.OSSClient;import com.aliyun.oss.common.utils.BinaryUtil;import com.aliyun.oss.model.*;import org.slf4j.Logger;import o......

经常把天聊死的胖子
8分钟前
1
0
Windows系统中eclipse修改字体为Courier New

背景:在eclipse修改字体时没有找到Courier New字体; 解决: 1.在计算机地址栏上输入“C:\Windows\Fonts”路径,回车打开Win10字体文件夹。查看是否有Courier New字体;如下图: 2.如果有该...

anlve
8分钟前
1
0
使用hexo做博客网站

hexo有什么用? hexo 可以把md文件生成html静态网页。 hexo官网:https://hexo.io/zh-cn/ 本地安装hexo。 npm install -g hexo-cli#生成blog(名字任意)文件夹,并且在这个文件夹里面初始化...

王坤charlie
8分钟前
1
0
RabbitMQ+PHP 教程四(Routing)用yii2测试通过

开始 在本教程中,我们将为它添加一个特性——我们将只可能订阅消息的一个子集。例如,我们只能够将关键错误消息直接指向日志文件(以节省磁盘空间),同时仍然能够打印控制台上的所有日志消...

hansonwong
13分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部