POJ 1742 Coins ( 经典多重部分和问题 && DP || 多重背包 )
题意 : 有 n 种面额的硬币,给出各种面额硬币的数量和和面额数,求最多能搭配出几种不超过 m 的金额?
分析 :
这题可用多重背包来解,但这里不讨论这种做法。
如果之前有接触过背包DP的可以自然想到DP数组的定义 ==> dp[i][j] 表示使用前 i 种硬币是否可以凑成面额 j 。
根据这样的定义,则一开始初始化 dp[0][0] = true 最后统计 dp[n][1 ~ m] 为 true 的数量即为答案
状态转移方程为 dp[i][j] |= dp[i-1][ j - k*val[i] ] ( k 表示取 k 个第 i 种硬币、val[i] 表示第 i 种硬币的面额 )
转移方程的意义不难理解,需要考虑当前的 dp[i][j] 可以从哪些状态转移而来,如下
使用第 i 种硬币刚好凑成 j 的值应当为上个状态( dp[i-1][] )合法的 j-val[i]、j-2*val[i]、j-3*val[i]....
故代码应当为一个如下所示的三重循环,但是复杂度较高无法通过这题.....
#include<stdio.h> #include<algorithm> #include<string.h> using namespace std; ; ]; int num[maxn], val[maxn]; int main(void) { int N, C; && C==)){ ; i<=N; i++) scanf("%d", &val[i]); ; i<=N; i++) scanf("%d", &num[i]); memset(dp, false, sizeof(dp)); dp[][] = true; ; i<=N; i++){ ; j<=C; j++){ ; k<=num[i] && k*val[i]<=j; k++){ dp[i][j] |= dp[i-][j-k*val[i]]; } } } printf(, dp[N]+C+, true)); } ; }
通常使用 dp 数组只记录布尔值是种浪费的做法,一般就去考虑在保证正确性的情况下改变 dp 含义记录更多信息去降低复杂度!
现将 dp 含义改变为 ==> dp[i][j] 表示用前 i 种硬币凑成 j 时第 i 种硬币最多还可以剩多少
挑战书上是直接给出了定义,但是我更乐于探寻这玩意是什么来的? 注:以下都是我自己的想法
想想上面的解法,好像会发现其实如果我当前考虑过 dp[i][j] = true 了,那么 dp[i][j+val[i]]、dp[i][j+2*val[i]]、dp[i][j+3*val[i]]... 应该都为 true
而枚举 j 的顺序也恰好是从小到大,所以必定会枚举到 dp[i][j+val[i]]、dp[i][j+2*val[i]]...,所以何不写成如下这样
; i<=N; i++){ ; j<=C; j++){ dp[j] |= dp[j-val[i]]; } }
运行了样例之后发现这样的做法得出的答案比标准答案更大!为什么?因为这样的做法没有考虑到数量,一种硬币的数量是有限的
所以当 j+k*val[i] 的 k 超过了规定数量的时候就会发生错误,使得一些本该为 false 的 dp 数组值变成了 true,所以我们需要记录数量!
复杂度为 O(n*m) 在 POJ 上跑了 2016MS
#include<stdio.h> #include<algorithm> #include<string.h> using namespace std; ; ]; int num[maxn], val[maxn]; bool fun(int x) { ) return true; return false; } int main(void) { int N, C; && C==)){ ; i<=N; i++) scanf("%d", &val[i]); ; i<=N; i++) scanf("%d", &num[i]); memset(dp, -, sizeof(dp)); dp[] = ; ; i<=N; i++){ ; j<=C; j++){ ) dp[j] = num[i]; ) dp[j] = -; ; } } printf(, dp++C, fun)); } ; }
最新文章
- [LeetCode] 14. Longest Common Prefix
- sql server 链接到本地实例出错
- DB2不记录事务日志
- Android: 触屏fling/scroll/drag的区别及其详细过程
- 使用spring手动控制事务
- uva10020 贪心
- 表单同时有中文字段和文件上传,加上enctype=";multipart/form-data";后导致的中文乱码问题
- js数组练习
- Dalvik虚拟机的优化机制
- 在visual studio的工程项目应用中打开console控制窗口
- 读外部存储的权限READ_EXTERNAL_STORAGE
- ZooKeeper 01 - 什么是ZooKeeper + 部署ZooKeeper集群
- Android studio和Genymotion-VirtualBox的配合使用
- Ubuntu下安装sbt
- init_ir_技术实现篇
- 安卓开发_浅谈TimePicker(时间选择器)
- python gui messagebox
- Django + Uwsgi + Nginx 实现生产环境 项目部署
- django Rest Framework---缓存通过drf-extensions扩展来实现
- 说说HTML5中label标签的可访问性问题——张鑫旭