有N个货币,将其放入M个背包,使价值最大的背包和价值最小的背包的差值最小。 输入 第一行两个整数N,M .下一行N个整数,表示货币的价值。 输出 一行一个整数,表示最小的差距 的代码
时间: 2023-03-31 07:03:17 浏览: 60
这是一个经典的背包问题,可以使用动态规划来解决。
首先,将货币按照价值从大到小排序,然后依次将货币放入背包中。对于每个货币,可以选择放入当前价值最小的背包或者放入当前价值最大的背包。具体来说,设dp[i][j]表示前i个货币放入j个背包时,最小的差距是多少。则有以下状态转移方程:
dp[i][j] = min(dp[i-1][j], dp[i-1][j-1] + 2*val[i-1] - sum[i-1]/m)
其中,val[i-1]表示第i个货币的价值,sum[i-1]表示前i个货币的总价值,m表示背包的数量。注意,当i<=j时,dp[i][j]的值为,因为此时每个背包都至少有一个货币。
最终的答案即为dp[n][m]。
以下是完整的代码实现:
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 105, M = 105;
int n, m;
int val[N], sum[N];
int dp[N][M];
int main()
{
cin >> n >> m;
for (int i = ; i < n; i ++ )
{
cin >> val[i];
}
sort(val, val + n, greater<int>());
for (int i = ; i < n; i ++ )
{
sum[i+1] = sum[i] + val[i];
}
memset(dp, x3f, sizeof dp);
for (int i = ; i <= n; i ++ )
{
dp[i][] = ;
}
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= min(i, m); j ++ )
{
dp[i][j] = min(dp[i-1][j], dp[i-1][j-1] + 2*val[i-1] - sum[i-1]/m);
}
}
cout << dp[n][m] << endl;
return ;
}
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)