华为笔试题 ：
给你5个物品 分别给定其价值，规定一个钱数，和每个物品的个数，求刚好花完钱最少使用的物品数
思路：
dp 感觉像背包的一个变种 dp[i][j] 表示前i个物品花完j 元所需要的最少物品数，那么dp[i][j]=min(dp[i][j],dp[i-1][j-k*v[i]]+k)
代码：
#include <iostream> #include <cstring> using namespace std; int dp[6][110]; int v[5]={1,3,7,11,13}; int nums[5]; int main(){ int m; for(int i=0;i<5;i++){ cin>>nums[i]; } cin>>m; memset(dp,0x3f3f3f3f,sizeof dp); for(int i=0;i<=5;i++){ dp[i][0]=0; } for(int i=1;i<=5;i++){ for(int j=1;j<=m;j++){ dp[i][j]=0x3f3f3f3f; for(int k=0;k*v[i-1]<=j&&k<=nums[i-1];k++){ dp[i][j]=min(dp[i][j],dp[i-1][j-k*v[i-1]]+k); } } } cout<<dp[5][m]<<endl; }
原文：https://www.cnblogs.com/kstranger/p/13394391.html