多重背包问题--最少数量硬币
作者:
黎虽无意逐鹿
,
2022-11-09 19:23:30
,
所有人可见
,
阅读 183
给定集合T[1~n] c[1~n] 表示面值为T[i] ,数量为c[i]的硬币集合, 给定m元,请你用最少数量的硬币拼凑出m元,如果凑不出来输出-1,否则输出最少硬币数量
#include<bits/stdc++.h>
using namespace std;
const int N = 1010 ;
#define INF 0x3f3f3f3f
int T[N] , c[N] , f[N];
int n,m;
int main()
{
cin>>n;
for(int i = 0 ; i < n ; i ++ )scanf("%d%d",&T[i],&c[i]);
cin>>m;
//初始化集合f[i] 表示装下总体积为i消耗最小数量的集合
memset(f, 0x3f , sizeof f);
f[0] = 0 ;//总体积为0的背包最小数量自然是0
for(int i = 0 ; i < n ; i++) // 枚举面值 T[i]
for(int j = 1 ; j <= c[i] ; j++) //枚举个数
for(int k = m ; k >= T[i] ; k--) //枚举体积
f[k] = min(f[k] , f[k-T[i]] + 1);
if(f[m] < INF) cout << f[m] << endl;
else puts("-1");
return 0;
}
未优化前的状态计算: f[i][j] = min(f[ i - 1][ j ],f[ i -1][j - T[ i ] ] +1);
优化后 f[ j ] = min(f[ j ] ,f[ j - T[ i ]] + 1);