[学习笔记]背包问题(一)

时间:2022-11-01 18:42:23

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