首页 > 分享 > 多功能恒温宠物背包的制作方法

多功能恒温宠物背包的制作方法

萌宠菠菠乐园
2024-09-19 13:07

DP - 二维费用背包 - 宠物小精灵之收服

题意：

小智有 n 个精灵球， m 为皮卡丘的体力值， k 为野生小精灵的数量。小智有n个精灵球，m为皮卡丘的体力值，k为野生小精灵的数量。小智有n个精灵球，m为皮卡丘的体力值，k为野生小精灵的数量。

输入 k 个组数据，每组包括收服该小精灵所需的精灵球数量 C 以及该小精灵的体力值 R 。输入k个组数据，每组包括收服该小精灵所需的精灵球数量C以及该小精灵的体力值R。输入k个组数据，每组包括收服该小精灵所需的精灵球数量C以及该小精灵的体力值R。

收服每个小精灵需要花费 C 个精灵球，同时皮卡丘的体力值会减去 R 。收服每个小精灵需要花费C个精灵球，同时皮卡丘的体力值会减去R。收服每个小精灵需要花费C个精灵球，同时皮卡丘的体力值会减去R。

若皮卡丘的体力值小于等于 0 ，则收服失败。若皮卡丘的体力值小于等于0，则收服失败。若皮卡丘的体力值小于等于0，则收服失败。

现要求在收服小精灵数量最大的前提下，皮卡丘剩余的体力值尽量的大。输出所需花费的精灵球数量以及皮卡丘剩余的体力值。现要求在收服小精灵数量最大的前提下，皮卡丘剩余的体力值尽量的大。\输出所需花费的精灵球数量以及皮卡丘剩余的体力值。现要求在收服小精灵数量最大的前提下，皮卡丘剩余的体力值尽量的大。输出所需花费的精灵球数量以及皮卡丘剩余的体力值。

分析：

将精灵球数量 n 和皮卡丘体力值 m 视作背包的两个容量， k 个小精灵视作 k 件物品。将精灵球数量n和皮卡丘体力值m视作背包的两个容量，k个小精灵视作k件物品。将精灵球数量n和皮卡丘体力值m视作背包的两个容量，k个小精灵视作k件物品。

问题转化为：在背包容量 V 1 不超过 n ， V 2 不超过 m 的情况下，尽量从 k 个物品拿更多的物品，且 V 1 的余量尽量大。变成了二维费用背包问题。问题转化为：在背包容量V_1不超过n，V_2不超过m的情况下，\尽量从k个物品拿更多的物品，且V_1的余量尽量大。变成了二维费用背包问题。问题转化为：在背包容量V1不超过n，V2不超过m的情况下，尽量从k个物品拿更多的物品，且V1的余量尽量大。变成了二维费用背包问题。

状态表示： f [ i ] [ j ] [ k ] ：考虑前 i 件物品，且体积不超过 j ，重量不超过 k ，能够选择的物品数量的最大值。状态计算： ① 、不包含第 i 个物品： f [ i ] [ j ] [ k ] = f [ i − 1 ] [ j ] [ k ] 。 ② 、包含第 i 个物品： f [ i ] [ j ] [ k ] = f [ i − 1 ] [ j − v 1 [ i ] ] [ k − v 2 [ i ] ] + 1 。状态表示：f[i][j][k]：考虑前i件物品，且体积不超过j，重量不超过k，能够选择的物品数量的最大值。\状态计算：\①、不包含第i个物品：f[i][j][k]=f[i-1][j][k]。\②、包含第i个物品：f[i][j][k]=f[i-1][j-v_1[i]][k-v_2[i]]+1。状态表示：f[i][j][k]：考虑前i件物品，且体积不超过j，重量不超过k，能够选择的物品数量的最大值。状态计算：①、不包含第i个物品：f[i][j][k]=f[i−1][j][k]。②、包含第i个物品：f[i][j][k]=f[i−1][j−v1[i]][k−v2[i]]+1。

那么最终精灵球的最小花费就是 f [ k ] [ n ] [ m ] ，皮卡丘消耗的最小体力值就是满足 f [ k ] [ n ] [ x ] = f [ k ] [ n ] [ m ] 的最小 x ， 0 < = x < = m 。那么最终精灵球的最小花费就是f[k][n][m]，皮卡丘消耗的最小体力值就是满足f[k][n][x]=f[k][n][m]的最小x，\0<=x<=m。那么最终精灵球的最小花费就是f[k][n][m]，皮卡丘消耗的最小体力值就是满足f[k][n][x]=f[k][n][m]的最小x，0<=x<=m。

需要注意的是：

皮卡丘的体力值必须严格大于 0 ，因此背包第三维度的最大容量应当是 m − 1 。皮卡丘的体力值必须严格大于0，因此背包第三维度的最大容量应当是m-1。皮卡丘的体力值必须严格大于0，因此背包第三维度的最大容量应当是m−1。

同样可以优化到二维，第二层和第三层容量均从大到小循环。同样可以优化到二维，第二层和第三层容量均从大到小循环。同样可以优化到二维，第二层和第三层容量均从大到小循环。

代码：

#include<iostream> #include<algorithm> using namespace std; const int N=1010,M=510; int n,m,k; int f[N][M]; int main() { cin>>n>>m>>k; for(int i=1;i<=k;i++) { int v1,v2; cin>>v1>>v2; for(int j=n;j>=v1;j--) for(int u=m-1;u>=v2;u--) f[j][u]=max(f[j][u],f[j-v1][u-v2]+1); } cout<<f[n][m-1]<<' '; int pos=m-1; while(pos>0&&f[n][pos-1]==f[n][m-1]) pos--; cout<<m-pos<<endl; return 0; }

1234567891011121314151617181920212223242526272829