摘要：
一、问题描述 物品无限的背包问题：有n种物品，每种均有无穷多个。第 i 种物品的体积为Vi,重量为Wi。选一些物品装到一个容量为 C 的背包中，求使得背包内物品总体积不超过C的前提下重量的最大值。1≤n≤100, 1≤Vi≤C≤10000, 1≤Wi≤1000000. 二、解题思路 我们可以先求体积 阅读全文
posted @ 2018-08-08 23:12
Rogn
阅读(948)
评论(0)
推荐(0)
摘要：
一、问题描述 有n种硬币，面值分别为V1,V2,V3,...,Vn,每种都有无限多。给定非负整数S,可以选用多少硬币，使得面值之和恰好为S?输出硬币数目的最小值和最大值。1≤n≤100,0≤S≤10000,1≤Vi≤S. 二、解题思路 将每种面值看作一个点，表示“还需凑足的面值”，则初始状态为S，目 阅读全文
posted @ 2018-08-08 20:56
Rogn
阅读(487)
评论(0)
推荐(0)
摘要：
一、DAG的介绍 Directed Acyclic Graph,简称DAG,即有向无环图，有向说明有方向，无环表示不能直接或间接的指向自己。 摘录：有向无环图的动态规划是学习动态规划的基础，很多问题都可以转化为DAG上的最长路、最短路或路径计数问题。 通常需要建图，不复杂的也可以当最长上升子序列处理 阅读全文
posted @ 2018-08-08 17:55
Rogn
阅读(672)
评论(0)
推荐(0)
摘要：
一、问题 有一个长为n的数列 a0,a1,a2...,an-1a。请求出这个序列中最长的上升子序列的长度和对应的子序列。上升子序列指的是对任意的i < j都满足ai < aj的子序列。 二、思路 如果i < j且ai < aj则认为ai到aj存在有向边，由于一个数不可能直接或间接的指向自己，所以是一 阅读全文
posted @ 2018-08-08 15:35
Rogn
阅读(379)
评论(0)
推荐(0)
浙公网安备 33010602011771号