首页 > 代码库 > [学习笔记]背包问题(一)
[学习笔记]背包问题(一)
01背包
有件物品和一个容量为的背包.第件物品体积为,价值为.
求背包最大价值.
表示前种物品体积为的最大价值,
.
时间复杂度.
- 优化空间复杂度
表示体积为的最大价值,
(从大到小枚举).
多重背包
有件物品和一个容量为的背包。第种物品最多有件可用,体积为,价值为.求背包最大价值.
表示前种物品体积为的最大价值,
时间复杂度.
- 二进制拆分
将拆成,
则在其中任意选取多个数,其和
间的数都可以通过选取其中多个数得到.
证明:
因为每个十进制数都可拆成二进制数,分别代表二进制某一位上的,
所以间的数都可以取到.
加上后,间的数都可以取到.
因为,即,
所以,即.
所以.
例题
Description
设有的砝码各若干枚(其总重)要求:计算用这些砝码能称出的不同重量的个数,但不包括一个砝码也不用的情况。
Input
一行,包括六个正整数,表示砝码有个,砝码有个...砝码有个。相邻两个整数之间用单个空格隔开。
Output
以的形式输出,其中为可以称出的不同重量的个数。
Sample Input
1 1 0 0 0 0
Sample Output
Total=3
Solution
多重背包二进制拆分+注意输出格式。
#include<cmath> #include<ctime> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define N 105 #define M 100005 using namespace std; int a[7]={0,1,2,3,5,10,20}; int w[N],n,ans;bool f[N][M]; inline void init(){ for(int i=1,s,k;i<=6;++i){ scanf("%d",&s);k=s; for(int j=1;k>=j;j<<=1,k>>=1){ w[++n]=j*a[i];s-=j; } if(s) w[++n]=s*a[i]; } f[0][0]=true; for(int i=1;i<=n;++i){ for(int j=0;j<w[i];++j) f[i][j]=f[i-1][j]; for(int j=w[i];j<M;++j) f[i][j]=(f[i-1][j]||f[i-1][j-w[i]]); } for(int j=1;j<M;++j) if(f[n][j]) ++ans; printf("Total=%d\n",ans); } int main(){ freopen("weight.in","r",stdin); freopen("weight.out","w",stdout); init(); fclose(stdin); fclose(stdout); return 0; }
- 单调队列优化
观察式子,
每一个的值相同的可以用单调队列进行优化.
例题 bzoj1531
完全背包
有件物品和一个容量为的背包.每种物品都有无限件可用,第件物品体积为,价值为.求背包最大价值.
表示前种物品体积为的最大价值.
.
时间复杂度
- 优化时间复杂度
.
例题 bzoj1618
[学习笔记]背包问题(一)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。