装箱问题+宠物小精灵之收服+数字组合——01背包

一、装箱问题 (裸题)

有一个箱子容量为 V，同时有 n 个物品，每个物品有一个体积（正整数）。
要求 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入
第一行是一个整数 V (0 < V ≤ 20000)，表示箱子容量。
第二行是一个整数 n (0 < n ≤ 30)，表示物品数。
接下来 n 行，每行一个正整数（不超过10000），分别表示这 n 个物品的各自体积。
输出
一个整数，表示箱子剩余空间。

Input
24
6
8
3
12
7
9
7
Output
0

解析：
求所剩空间最小，可转化成所用空间最大。
每个物品的价值就是体积。
就可转化成 从前 n 个物品中，不超过总体积，最大价值是多少。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=2e6+10;
int n,u;
int v[N];
int f[N];
void solve()
{cin>>u>>n;for (int i=1;i<=n;i++) cin>>v[i];for (int i=1;i<=n;i++)for (int j=u;j>=v[i];j--)f[j]=max(f[j],f[j-v[i]]+v[i]);cout<<u-f[u];
}
signed main()
{ios;int T=1;//cin>>T;while (T--) solve();return 0;
}

 二、 宠物小精灵之收服 (二维费用)

宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。
一天，小智和皮卡丘来到了小精灵狩猎场，里面有很多珍贵的野生宠物小精灵。
小智也想收服其中的一些小精灵。
然而，野生的小精灵并不那么容易被收服。
对于每一个野生小精灵而言，小智可能需要使用很多个精灵球才能收服它，而在收服过程中，野生小精灵也会对皮卡丘造成一定的伤害（从而减少皮卡丘的体力）。
当皮卡丘的体力小于等于0时，小智就必须结束狩猎（因为他需要给皮卡丘疗伤），而使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服。
当小智的精灵球用完时，狩猎也宣告结束。
我们假设小智遇到野生小精灵时有两个选择：收服它，或者离开它。
如果小智选择了收服，那么一定会扔出能够收服该小精灵的精灵球，而皮卡丘也一定会受到相应的伤害；如果选择离开它，那么小智不会损失精灵球，皮卡丘也不会损失体力。
小智的目标有两个：主要目标是收服尽可能多的野生小精灵；如果可以收服的小精灵数量一样，小智希望皮卡丘受到的伤害越小（剩余体力越大），因为他们还要继续冒险。
现在已知小智的精灵球数量和皮卡丘的初始体力，已知每一个小精灵需要的用于收服的精灵球数目和它在被收服过程中会对皮卡丘造成的伤害数目。
请问，小智该如何选择收服哪些小精灵以达到他的目标呢？

输入
输入数据的第一行包含三个整数：N (0 < N ≤ 1000)，M (0 < M ≤ 500)，K (0 < K ≤ 100)，分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。
之后的K行，每一行代表一个野生小精灵，包括两个整数：收服该小精灵需要的精灵球的数量，以及收服过程中对皮卡丘造成的伤害。

输出
输出为一行，包含两个整数：C，R，分别表示最多收服C个小精灵，以及收服C个小精灵时皮卡丘的剩余体力值最多为R。

Input
10 100 5
7 10
2 40
2 50
1 20
4 20
Output
3 30

int n,u,k;

int v1[N],v2[N],f[N][N][N],s[N][N][N];

void solve()

{

    cin>>u>>k>>n;

    for (int i=1;i<=n;i++) cin>>v1[i]>>v2[i];

    for (int i=1;i<=n;i++)

    for (int j=1;j<=u;j++)

    for (int l=1;l<k;l++)

    {

        f[i][j][l]=f[i-1][j][l];

        s[i][j][l]=s[i-1][j][l];

        if (j-v1[i]>=0&&l-v2[i]>=0)

        {

            if (f[i][j][l]<f[i-1][j-v1[i]][l-v2[i]]+1) f[i][j][l]=f[i-1][j-v1[i]][l-v2[i]]+1,s[i][j][l]=s[i-1][j-v1[i]][l-v2[i]]+v2[i];

            else if (f[i][j][l]==f[i-1][j-v1[i]][l-v2[i]]+1&&s[i][j][l]>s[i-1][j-v1[i]][l-v2[i]]+v2[i]) s[i][j][l]=s[i-1][j-v1[i]][l-v2[i]]+v2[i];

        }

    }

    cout<<f[n][u][k-1]<<" "<<k-s[n][u][k-1];

}

解析：
题目很长，但是能看出来是01背包问题，不过是多加了一维。
所求 从前n个小精灵中选 在不超过小智精灵球的数量，对皮卡丘的伤害值小于体力值的情况下，尽可能地多收服小精灵，最多能收服多少小精灵，和皮卡丘体力剩余最大。
正常是三维 f[i][j][k], 不过空间肯定不够，所以得优化代码，降一维就可以了。

//代码一:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=1010;
int n,u,k;
int v1[N],v2[N],f[N][N],s[N][N];
void solve()
{cin>>u>>k>>n;for (int i=1;i<=n;i++) cin>>v1[i]>>v2[i];for (int i=1;i<=n;i++)for (int j=u;j>=v1[i];j--)for (int l=k-1;l>=v2[i];l--){if (f[j][l]<f[j-v1[i]][l-v2[i]]+1) f[j][l]=f[j-v1[i]][l-v2[i]]+1,s[j][l]=s[j-v1[i]][l-v2[i]]+v2[i];else if (f[j][l]==f[j-v1[i]][l-v2[i]]+1&&s[j][l]>s[j-v1[i]][l-v2[i]]+v2[i]) s[j][l]=s[j-v1[i]][l-v2[i]]+v2[i];}cout<<f[u][k-1]<<" "<<k-s[u][k-1];
}
signed main()
{ios;int T=1;//cin>>T;while (T--) solve();return 0;
}//代码二 (更简便)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=1010;
int n,u,k;
int v1[N],v2[N],f[N][N];
void solve()
{cin>>u>>k>>n;for (int i=1;i<=n;i++) cin>>v1[i]>>v2[i];for (int i=1;i<=n;i++)for (int j=u;j>=v1[i];j--)for (int l=k-1;l>=v2[i];l--){f[j][l]=max(f[j][l],f[j-v1[i]][l-v2[i]]+1);}cout<<f[u][k-1]<<" ";int cnt=k-1;for (int i=k-1;i>=0;i--){if (f[u][i]==f[u][k-1]) cnt=i;}cout<<k-cnt;
}
signed main()
{ios;int T=1;//cin>>T;while (T--) solve();return 0;
}

三、数字组合 (方案数)

给定 N 个正整数 A1,A2,…,AN，从中选出若干个数，使它们的和为 M，求有多少种选择方案。

输入
第一行包含两个整数 N 和 M (1 ≤ N ≤ 100,1 ≤ M ≤ 10000)。
第二行包含 N 个整数，表示 A1,A2,…,AN(1 ≤ Ai ≤ 1000)。
输出
包含一个整数，表示可选方案数。

Input
4 4
1 1 2 2
Output
3

 解析：
将 M 看成背包总体积
将每个数看成每个物品
所求 从前 n 个物品中选，恰好总体积是 M 的集合   的方案数。
状态转移：f[i][j]=f[i-1][j]+f[i-1][j-v[i]];
不过要记住要初始化哦！！

//代码一
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=110,M=1e4+10;
int n,m;
int v[N],f[N][M];
void solve()
{cin>>n>>m;for (int i=1;i<=n;i++) cin>>v[i];for (int i=0;i<=n;i++) f[i][0]=1;       //初始化for (int i=1;i<=n;i++)for (int j=1;j<=m;j++){f[i][j]=f[i-1][j];if (j-v[i]>=0) f[i][j] +=f[i-1][j-v[i]];}cout<<f[n][m];
}
signed main()
{ios;int T=1;//cin>>T;while (T--) solve();return 0;
}//代码二 (降一维)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=1e4+10;
int n,m;
int f[N],v[N];
void solve()
{cin>>n>>m;for (int i=1;i<=n;i++) cin>>v[i];f[0]=1;for (int i=1;i<=n;i++)for (int j=m;j>=v[i];j--)f[j] +=f[j-v[i]];cout<<f[m];
}
signed main()
{ios;int T=1;//cin>>T;while (T--) solve();return 0;
}