有重量分别为3,5,7公斤的三种货物,和一个载重量为X公斤的箱子(不考虑体积等其它因素,只计算重量)ios
须要向箱子内装满X公斤的货物,要求使用的货物个数尽量少(三种货物数量无限)spa
输入箱子载重量X(1 <= X <= 10000),一个整数。
若是没法装满,输出 -1。 若是能够装满,输出使用货物的总个数。
示例1code
4
-1
没法装满
#include <iostream> #include <algorithm> using namespace std; const int N = 100100; int dp[N]; const int nums[] = {3,5,7}; int main() { int n; cin>>n; for(int i=0;i<=n;i++) dp[i]=-1; dp[3] = 1; dp[5] = 1; dp[7] = 1; for(int i=6;i<=n;i++){ int temp = N; for(int j=0;j<3;j++){ if(i-nums[j]>=0 && dp[i-nums[j]]!=-1) temp = min(temp,dp[i-nums[j]]+1); } if(temp!=N) dp[i] = temp; } cout<<dp[n]<<endl; }