【精讲】经典问题——0/1背包问题

在n件物品取出若干件放在空间为W的背包里,

每件物品的体积为W1,W2至Wn,

与之相对应的价值为P1,P2至Pn,

对于每个物品只需要考虑选与不选两种情况,

求解将哪些物品装入背包可使价值总和最大。


背包问题,是DP中的经典题型,

而0/1背包是经典中的经典


建议阅读:
B站大佬开讲

百科:记忆化搜索

百科:动态规划

模板题:
vijos 0/1背包

进阶练习:

vijos 1104:采药

vijos 完全背包问题

扩展挑战:

vijos 开心的金明

vijos 搭配购买

可以更好了解和练习


如何做这道题呢?

孔子曰:题目不会就深搜递归

代码1 暴力出奇迹(不建议提交)

#include<bits/stdc++.h>
using namespace std;
int n,ans,m;
int w[1001],c[1001];
void dfs(int t,int q,int k)
{
	if(t>n)//选完
	{
		if(k>ans) ans=k;
		return;
	}
	dfs(t+1,q,k);
	if(q+w[t]<=m)dfs(t+1,q+w[t],k+c[t]);//可以就尝试
	return;
}
int main()
{
	cin>>m>>n;
	for(int i=1;i<=n;i++)cin>>w[i]>>c[i];
	dfs(1,0,0);
	cout<<ans;
	return 0;
}

【孔子】因炸服务器被封号


明显,本题递归会裂开(时间超限)

本题每次递归同一个参数得出的值相同,而出现了反复对同一个参数的递归

对于这种问题,记忆化搜索是一个好的解决方案,并可以AC

f[n][m]表示选到第n个物品,背包用了m时得到的最大价值

代码2: 记忆化搜索

#include<bits/stdc++.h>
using namespace std;
int n,ans,m;
int w[1005],c[1005];
int f[110][1005];//f[n][m]表示选到第n个物品,背包用了m时得到的最大价值

void dfs(int t,int q,int k)
{
	if(t>n)
	{
		if(k>ans) ans=k;
		return;
	}
	if(f[t][q]<=k)
	{
		f[t][q]=k;
		dfs(t+1,q,k);
		if(q+w[t]<=m)dfs(t+1,q+w[t],k+c[t]);
	}
	return ;
}

int main()
{
	cin>>m>>n;
	for(int i=1;i<=n;i++)cin>>w[i]>>c[i];
	dfs(1,0,0);
	cout<<ans;
	return 0;
}

本题虽然可以用记忆化搜索AC,

但明显不是最优解。


既然已经可以记忆化搜索了,

那就满足无后效性和阶段性,可以DP求解

f[n][m]表示选到第n个物品,背包用了m时得到的最大价值

从前向后直接枚举,可以放就看是不是当前最优解(是不是最大)

代码3: 二维动态规划

#include<bits/stdc++.h>
using namespace std;
int  f[1001][1001],w,c,n,m;
int main()
{
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&w,&c);
		for(int k=0;k<=m;k++)//注意是从0开始!
		{
			f[i][k]=f[i-1][k];
			if(k>=w) f[i][k]=max(f[i][k],f[i-1][k-w]+c);
		}
	}
	printf("%d",f[n][m]);
	return 0;
}

假设n和m>=10000,那么这种方法就没用了,

好在天无绝人之路——STL中有个vector,

不过更简单的方法是用滚(渣)动(男)数组


可以发现,f的第一层只使用了i,i-1,m三层,

那如果用一个一维数组,只有f[m]呢?

压力马斯内(赞赏)


在修改第i次前,数组的值就是i-1,直接调用修改,

结束后,f[m]正是原来的f[n][m](当前是第n次修改)

那直接一维啊!


但是,一维时要倒序枚举,

不然就会使用多次(不符合0/1性质,成了完全背包),

而且是for m~w 这个很好理解吧

代码4:一维动态规划

#include<cstdio>
using namespace std;
int n,t,w,v,f[1001];
int max(int x,int y){
	if(x>y)return x;
	else return y;
}
int main(){
	scanf("%d%d",&n,&t);
	for(int i=1;i<=t;i++)
	{
		scanf("%d%d",&w,&v);
		for(int j=n;j>=w;j--)
			f[j]=max(f[j],f[j-w]+v);		
	}
	printf("%d",f[n]);
}

那么关于0/1背包的讲解就结束了,

如有不对,务必提出

上一篇:1001——MySql练习


下一篇:PAT 甲级 1001 A+B Format (20 分)(Java)