3.9 多重背包

本文主要是介绍3.9 多重背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

代码随想录 (programmercarl.com)

56. 携带矿石资源（第八期模拟笔试） (kamacoder.com)

56. 携带矿石资源（第八期模拟笔试）

时间限制：5.000S  空间限制：256MB

题目描述

你是一名宇航员，即将前往一个遥远的行星。在这个行星上，有许多不同类型的矿石资源，每种矿石都有不同的重要性和价值。你需要选择哪些矿石带回地球，但你的宇航舱有一定的容量限制。 

给定一个宇航舱，最大容量为 C。现在有 N 种不同类型的矿石，每种矿石有一个重量 w[i]，一个价值 v[i]，以及最多 k[i] 个可用。不同类型的矿石在地球上的市场价值不同。你需要计算如何在不超过宇航舱容量的情况下，最大化你所能获取的总价值。

输入描述

输入共包括四行，第一行包含两个整数 C 和 N，分别表示宇航舱的容量和矿石的种类数量。 

接下来的三行，每行包含 N 个正整数。具体如下： 

第二行包含 N 个整数，表示 N 种矿石的重量。 

第三行包含 N 个整数，表示 N 种矿石的价格。 

第四行包含 N 个整数，表示 N 种矿石的可用数量上限。

输出描述

输出一个整数，代表获取的最大价值。

输入示例

10 3
1 3 4
15 20 30
2 3 2

输出示例

90

1.状态描述

dp[i][j]表示前i个物品在背包空间为j时的最大价值

2.状态转移 （有kNum[i]种选择，可以选择拿0-kNum[i]个物品）

            dp[i][j]=dp[i-1][j];for(int k=0;k<=kNum[i];k++){if(j>=k*wight[i]) dp[i][j]=max(dp[i-1][j-k*wight[i]]+k*value[i],dp[i][j]); else break;}

3. 初始化（第一行即可）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int getMaxValue(int m,int n,vector<int> wight,vector<int> value,vector<int> kNum)
{   vector<vector<int>> dp(n,vector<int>(m+1,0));for(int i=m;i>=wight[0];i--){for(int k=0;k<=kNum[0];k++){if( i>= k*wight[0]) dp[0][i]=max(dp[0][i-k*wight[0]]+k*value[0],dp[0][i]); else break;}}for(int i=1;i<n;i++){for(int j=m;j>=wight[0];j--){//状态转移 kNum[i]种选择，可以选择拿0-kNum[i]个物品dp[i][j]=dp[i-1][j];for(int k=0;k<=kNum[i];k++){if(j>=k*wight[i]) dp[i][j]=max(dp[i-1][j-k*wight[i]]+k*value[i],dp[i][j]); else break;}}}// for(int i=0;i<n;i++)// {//     for(int j=0;j<=m;j++)//     {//         cout<<dp[i][j]<<" ";//     }//     cout<<endl;// }return dp[n-1][m];
}
int main()
{int m,n;cin>>m>>n;int tempN=n;vector<int> wight,value,kNum;while(tempN--){int w;cin>>w;wight.push_back(w);}tempN=n;while(tempN--){int v;cin>>v;value.push_back(v);}tempN=n;while(tempN--){int k;cin>>k;kNum.push_back(k);}// for(auto e : value) cout<<e<<" ";cout<<getMaxValue(m,n,wight,value,kNum);return 0;
}

这篇关于3.9 多重背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---