小学学校网站建设计划,wordpress博客示例,外贸公司代理,连云港做网站哪里好这道题有个小小的坎#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
