建设工程指数网站,陕西 做网站的公司,seo搜索引擎优化总结报告,网站每天更新的内容是内链吗这道题有个小小的坎#xff0c;就是低于5块不能选#xff0c;大于5块#xff0c;可以任意选#xff0c;所以就在初始条件判断一下剩余钱数#xff0c;然后如果大于5的话#xff0c;这时候就要用到贪心的思想#xff0c;只要大于等于5#xff0c;先找最大的那个#xf…这道题有个小小的坎就是低于5块不能选大于5块可以任意选所以就在初始条件判断一下剩余钱数然后如果大于5的话这时候就要用到贪心的思想只要大于等于5先找最大的那个然后剩下的再去用背包去选择这样的结果一定是最优的。因为最大的那个一定会被选中剩下多少钱都无所谓用背包可以获得剩下的最优解所以最后也是最优解 代码如下 1 #include cstdio2 #include cstring3 #include algorithm4 using namespace std;5 const int N 1006;6 int dp[N];7 int value[N];8 int main()9 {
10 int n;
11 while (scanf(%d, n) 1, n)
12 {
13 for (int i 0; i n; i)
14 scanf(%d, value[i]);
15 int v;
16 scanf(%d, v);
17 if (v 5)//如果初始条件都不满足直接输出金额
18 {
19 printf(%d\n, v);
20 continue;
21 }
22 sort(value, value n);//排序
23 memset(dp, 0, sizeof(dp));
24 //01背包
25 for (int i 0; i n - 1; i)
26 {
27 for (int j v - 5; j value[i]; j--)
28 if (dp[j] dp[j - value[i]] value[i])
29 dp[j] dp[j - value[i]] value[i];
30 }
31 printf(%d\n, v - dp[v - 5] - value[n - 1]);
32 }
33 return 0;
34 } 转载于:https://www.cnblogs.com/Howe-Young/p/4165858.html
