文章
4
粉丝
204
获赞
3
访问
12.3k
每个物品可以使用多次,这是完全背包的模板题。把给的目标钱数当成背包容量,每个面值的货币当成物品,由于物品数量不限,这就转化成了完全背包的问题。根据carl哥的动归五部曲,首先定义dp数组下标含义,dp[i][j]表示,当背包容量为j时,用前i个物品将背包装满最少需要多少物品,在这题里就是钱数为j时,用前i个硬币凑到钱数j最少需要多少个硬币。第二步确定递推关系式,根据第i个物品能不能装入背包分成两种情况,若不能装入,即当前背包容量j>当前物品的重量item[i],dp[i][j]就等于dp[i-1][j],若能装入,就可以选择装或者不装,取一个最小值,第三部确定初始条件,背包容量为0时多个个物品将其装满所需要的最小物品数都是0,所以dp[i][0]初始化成0,当没有物品的时候,背包容量不论多大,都不可能装满,所以最小物品数为INT_MAX,所以dp[0][j]初始化成INT_MAX,第四部确定dp数组遍历顺序,这里采用先物品再背包,第五步打印dp数组,这里不需要
#include<bits/stdc++.h>
using namespace std;
int main() {
int m;
while (cin>>m)
{
if (m == 0) break;
int k;
cin >> k;
int* item = new int[k + 1];
for (int i = 1; i <= k; i++) {
cin >> item[i];
&nb...
登录后发布评论
暂无评论,来抢沙发