2017网易秋招–7、买苹果 -云博客

2017网易秋招–7、买苹果

# 移动开发 2024-05-05 00:16 0 24 来源：云博客

题目描述：（DP问题）

小易去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供6个每袋和8个每袋的包装(包装不可拆分)。可是小易现在只想购买恰好n个苹果，小易想购买尽量少的袋数方便携带。如果不能购买恰好n个苹果，小易将不会购买。

输入描述:

输入一个整数n，表示小易想购买n(1 ≤ n ≤ 100)个苹果

输出描述:

输出一个整数表示最少需要购买的袋数，如果不能买恰好n个苹果则输出-1

输入例子:

输出例子:

思路：DP问题。首先dp[i] = min(dp[i],dp[i-a[j]+1)。输入苹果总个数，把dp初始为sum，这样保证最后dp[sum] = sum则没有可以正好sum的结果，否则输入dp[sum]

 1 #include <iostream> 2 using namespace std; 3 //dp[i] = min(dp[i],dp[i-a[j]+1) 4  5 int main() 6 { 7 int sum; 8 while(cin>>sum) 9  {10 int a[2] = {6,8};11 int dp[100];12 dp[0] = 0;//也是关键之处13 for(int i=1;i<100;i++)14  {15 dp[i] = sum;16  }17 for(int i=0;i<=sum;i++)18  {19 for(int j=0;j<2;j++)20  {21 if(i>=a[j] && dp[i-a[j]] + 1 < dp[i])22  {23 dp[i] = dp[i-a[j]]+1;24  }25  }26  }27 if(dp[sum] == sum)28 cout<<-1<<endl;29 else30 cout<<dp[sum]<<endl;31 return 0;32  }33 }