01背包问题

dp[i-1][j]指没纳入当前物品dp[i-1][j-c_i]+w_i指纳入当前物品并且是和j-c_i体积下的价值作和

滚动数组优化空间复杂度

[NOIP2005 普及组] 采药

辰辰是个天资聪颖的孩子他的梦想是成为世界上最伟大的医师。为此他想拜附近最有威望的医师为师。医师为了判断他的资质给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说“孩子这个山洞里有一些不同的草药采每一株都需要一些时间每一株也有它自身的价值。我会给你一段时间在这段时间里你可以采到一些草药。如果你是一个聪明的孩子你应该可以让采到的草药的总价值最大。”

如果你是辰辰你能完成这个任务吗

输入格式

第一行有 $2$ 个整数 $T$$1\le T\le 1000$和 $M$$1\le M\le 100$用一个空格隔开$T$ 代表总共能够用来采药的时间$M$ 代表山洞里的草药的数目。

接下来的 $M$ 行每行包括两个在 $1$ 到 $100$ 之间包括 $1$ 和 $100$的整数分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出在规定的时间内可以采到的草药的最大总价值。

样例输入 #1

70 3
71 100
69 1
1 2

样例输出 #1

3

提示

【数据范围】

• 对于 $30\%$ 的数据$M\le 10$
• 对于全部的数据$M\le 100$。

思路

• 纯模板题没什么好说的
• 但是一开始写的时候遇到了一点小问题。题目中说明了M最多不会超过100所以我一开始写的时候对于背包数组开的大小是[105]但是过不了到现在也没发现原因,但以后试着开大一点吧
• f 数组开的大小应该是以 V 为尺度

题解

#include<iostream>
using namespace std;
int f[10005],v[10005],w[10005];
int main(){
    int n,m;
    cin>>m>>n;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++){
        for(int k=m;k>=v[i];k--) f[k]=max(f[k],f[k-v[i]]+w[i]);
    }
    cout<<f[m];
    return 0;
}

多重背包问题

多重背包

有 n 种物品第 i 种物品有 x_i个每一个物品重量为 w_i 价值为 v_i 现有一个承重能力为 TT 的背包在不超过承重能力的情况下背包种最多能装多少价值的物品。

输入描述

第一行输入两个整数nT(1≤nT≤100)代表物品种类和背包承重能力。
接下来n行每行3个整数x_iw_iv_i(1≤x_iw_i≤201≤v_i≤200)描述一个物品分别代表物品的个数、物品的重量、物品的价值

输出描述

输出一行一个整数表示在不超过承重能力的情况下背包物品的最大价值

示例一
输入

2 8
4 2 100
2 4 100

输出

400

思路

• 纯模板题

题解

#include<bits/stdc++.h>
using namespace std;
int x[105],w[105],v[105],t,n,dp[105];
int main(){
    scanf("%d%d",&n,&t);
    for(int i=1;i<=n;++i) scanf("%d%d%d",&x[i],&w[i],&v[i]);
    for(int i=1;i<=n;++i){
        for(int j=t;j>=w[i];--j) for(int k=0;k<=min(x[i],j/w[i]);++k) dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i]);
    }
    printf("%d",dp[t]);
}

完全背包问题

[NOIP2018 提高组] 货币系统

在网友的国度中共有 $n$ 种不同面额的货币第 $i$ 种货币的面额为 $a[i]$你可以假设每一种货币都有无穷多张。为了方便我们把货币种数为 $n$、面额数组为 $a[\mathrm{1..}n]$ 的货币系统记作 $(n,a)$。

在一个完善的货币系统中每一个非负整数的金额 $x$ 都应该可以被表示出即对每一个非负整数 $x$都存在 $n$ 个非负整数 $t[i]$ 满足 $a[i]\times t[i]$ 的和为 $x$。然而 在网友的国度中货币系统可能是不完善的即可能存在金额 $x$ 不能被该货币系统表示出。例如在货币系统 $n=3$, $a=[2,5,9]$ 中金额 $1,3$ 就无法被表示出来。

两个货币系统 $(n,a)$ 和 $(m,b)$ 是等价的当且仅当对于任意非负整数 $x$它要么均可以被两个货币系统表出要么不能被其中任何一个表出。

现在网友们打算简化一下货币系统。他们希望找到一个货币系统 $(m,b)$满足 $(m,b)$ 与原来的货币系统 $(n,a)$ 等价且 $m$ 尽可能的小。他们希望你来协助完成这个艰巨的任务找到最小的 $m$。

输入格式

输入文件的第一行包含一个整数 $T$表示数据的组数。

接下来按照如下格式分别给出 $T$ 组数据。 每组数据的第一行包含一个正整数 $n$。接下来一行包含 $n$ 个由空格隔开的正整数 $a[i]$。

输出格式

输出文件共有 $T$ 行对于每组数据输出一行一个正整数表示所有与 $(n,a)$ 等价的货币系统 $(m,b)$ 中最小的 $m$。

样例输入 #1

2 
4 
3 19 10 6 
5 
11 29 13 19 17

样例输出 #1

2   
5

提示

在第一组数据中货币系统 $(2,[3,10])$ 和给出的货币系统 $(n,a)$ 等价并可以验证不存在 $m<2$ 的等价的货币系统因此答案为 $2$。 在第二组数据中可以验证不存在 $m<n$ 的等价的货币系统因此答案为 $5$。

【数据范围与约定】

对于 $100\%$ 的数据满足 $1\le T\le 20,n,a[i]\ge 1$。

思路

• 首先m,b中出现的数必须在n,a中出现
• n,a中最小的数肯定是m,b中必须出现的这个好理解因为最小的数没办法用其他的数表示而大的数往往可以通过小的数表示所以需要将给出的a数组排序一下然后从小到大找出 b 数组需要的数遍历时当前的数无法用已有的数进行表示的时候就将它纳入 b 数组内

题解

#include<bits/stdc++.h>
using namespace std;
int a[105],f[25005];
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,ans=0;
        scanf("%d",&n);
        for(int i=0;i<n;i++)cin>>a[i];
        sort(a,a+n);
        memset(f,0,sizeof f);
        f[0]=1;
        for(int i=0;i<n;i++){
            if(!f[a[i]])++ans;
            for(int j=a[i];j<=a[n-1];j++){
                f[j]=max(f[j],f[j-a[i]]);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}