能否给出证明呢?
by 早右昕 @ 2017-07-17 15:22:07
但局部最优解不一定是全局最优解吧
by 一念之间 @ 2017-07-20 08:50:11
这道题目经典的动态规划啊，因为满足无后效性原则，但是不能避免贪心算法的目光短浅的缺点。
by Hydra_ @ 2017-08-25 06:58:51
@[LKY2002](/space/show?uid=47638)
两台机器，两个分公司。
第一个分公司： 1台50,2台51
第二个分公司：1台1，2台233
显然全部给第二个啊
by 老K @ 2017-09-10 08:30:32
注意，矩阵是指第i个公司分配j台机器，不是第j台机器时的利润
by jtzhang @ 2018-03-11 09:54:36
你们要的贪心，过不了。```cpp
#include<iostream>
using namespace std;
int n,m,a[11][16],gs[11],cp[11];
int main()
{
int max,rc,tot=0;
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
for(int i=1;i<=m;i++)
{
max=-1;
for(int j=1;j<=n;j++)
{
cp[j]=a[j][gs[j]+1]-a[j][gs[j]];
if(cp[j]>max)
{
max=cp[j];
rc=j;
}
}
gs[rc]++;
tot+=max;
}
cout<<tot<<endl;
for(int i=1;i<=n;i++)
cout<<i<<" "<<gs[i]<<endl;
return 0;
}
```
by zerrun @ 2018-07-24 11:06:18
重新发一遍
```cpp
#include<iostream>
using namespace std;
int n,m,a[11][16],gs[11],cp[11];
int main()
{
int max,rc,tot=0;
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
for(int i=1;i<=m;i++)
{
max=-1;
for(int j=1;j<=n;j++)
{
cp[j]=a[j][gs[j]+1]-a[j][gs[j]];
if(cp[j]>max)
{
max=cp[j];
rc=j;
}
}
gs[rc]++;
tot+=max;
}
cout<<tot<<endl;
for(int i=1;i<=n;i++)
cout<<i<<" "<<gs[i]<<endl;
return 0;
}
```
by zerrun @ 2018-07-24 11:06:40