题目描述
总公司拥有 M 台 相同 的高效设备,准备分给下属的 N 个分公司。
各分公司若获得这些设备,可以为国家提供一定的盈利。盈利与分配的设备数量有关。
问:如何分配这M台设备才能使国家得到的盈利最大?
求出最大盈利值。
分配原则:每个公司有权获得任意数目的设备,但总台数不超过设备数 M。
输入格式
第一行有两个数,第一个数是分公司数 N,第二个数是设备台数 M;
接下来是一个 N×M 的矩阵,矩阵中的第 i 行第 j 列的整数表示第 i 个公司分配 j 台机器时的盈利。
输出格式
第一行输出最大盈利值;
接下 N 行,每行有 2 个数,即分公司编号和该分公司获得设备台数。
答案不唯一,输出任意合法方案即可。
样例
数据范围
1≤N≤10,
1≤M≤15
输入样例:
3 3
30 40 50
20 30 50
20 25 30
输出样例:
70
1 1
2 1
3 1
分组背包问题+求具体方案
说实话,这题题意不是容易看懂,直到认真看了一下样例才认出来是分组背包问题
题意可以转化成:给定一个容积为M的背包
从N组物品中选,总价值最大的选法
只是这里每组物品的个数也恰好是M,因此输入的矩阵就是$N\times M$了
C++ 代码
#include <iostream>
using namespace std;
const int N=11,M=16;
int w[N][M],dp[N][M],path[N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&w[i][j]);
正序的多重背包问题求解
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
{
dp[i][j]=dp[i-1][j];
for(int k=1;k<=j;k++)
dp[i][j]=max(dp[i][j],dp[i-1][j-k]+w[i][k]);
}
先输出收益的最大值
cout<<dp[n][m]<<endl;
顺序问题:因为要求具体方案,所以逆序推一遍,找出恰好符合条件的下标并输出
但是这里由于要求正序输出,但是倒序推导只能倒序输出
所以额外用了一个数path[]来存储结果
for(int i=n,j=m;i;i--)
meij
for(int k=1;k<=j;k++)
if(dp[i][j]==dp[i-1][j-k]+w[i][k]){
path[i]=k;
j-=k;
break;
}
for(int i=1;i<=n;i++)cout<<i<<' '<<path[i]<<endl;
return 0;
}