- 基本思路: 这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。 用子问题定义状态:即f[v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则 其状态转移方程便是:f[v]=max{f[v],f[v-c]+w}。 实现代码: …0顶 253浏览 2014-11-07 09:14:20分享
- [代码片段(50行)] 输出结果: [1, 9] [1, 2, 7] [1, 2, 3, 4] [1, 3, 6] [1, 4, 5] [2, 8] [2, 3, 5] [3, 7] [4, 6]…1顶 395浏览 2014-09-26 14:44:15分享
- 照做吧,幸好这个算法算100张票子也就是10秒不到,这还是mini-itx。 下面上算法,具体算法猛击这里(http://www.oiers.cn/pack/Index.html )和这里(http://zh.wikipedia.org/wiki/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98 )。输入是数字列表和目标,输出是组合和误差。f[i]是目前为止,最大…0顶 300浏览 2014-09-18 10:43:17分享
- 基本思路: 这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。 用子问题定义状态:即f[v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则 其状态转移方程便是:f[v]=max{f[v],f[v-c]+w}。 实现代码: …0顶 48301浏览 2014-09-17 09:20:35分享
- [代码片段(117行)] /* 5 27 8 3 12 7 10 5 8 4 15 9 5 27 8 8 12 12 10 10 8 8 15 15 5 26 8 8 12 12 10 10 8 8 15 15 5 28 8 8 12 12 10 10 8 8 15 15 5 29 8 8 12 12 10 10 8…0顶 72333浏览 2014-09-10 10:57:23分享
- 值得提及的一个问题是,在用 JAVA 实现时, 是按算法模型建模,还是用对象模型建模呢? 如果用算法模型,那么 背包的值、重量就直接存入二个数组里;如果用对象模型,则要对背包以及背包问题进行对象建模。思来想去,还是采用了对象模型,尽管心里感觉算法模型似乎更好一些。有时确实就是这样,对象模型虽然现在很主流,但也不是万能的,采用其它的模型和视角,或许可以得到更好的解法。 背包建模: …0顶 24784浏览 2014-08-17 09:20:47分享
- 【输入文件】 输入的第1 行,为两个正整数,用一个空格隔开: N m (其中N(<30000)表示总钱数,m(<25)为希望购买物品的个数。) 从第2 行到第m+1 行,第j 行给出了编号为j-1的物品的基本数据,每行有2 个非负整数 v p (其中v 表示该物品的价格(v≤10000),p 表示该物品的重要度(1~5)) 【输出文件】 输出只有一个正整数,为不超…0顶 24906浏览 2014-08-03 12:27:04分享
- 假如有物品如下: 物品号 物品名 重量 价钱 0 李子 4 4500 1 苹果 5 …0顶 74698浏览 2014-07-29 09:37:39分享
- [代码片段(50行)] 输出结果: [1, 9] [1, 2, 7] [1, 2, 3, 4] [1, 3, 6] [1, 4, 5] [2, 8] [2, 3, 5] [3, 7] [4, 6]…0顶 62616浏览 2014-07-24 15:34:15分享
- 值得提及的一个问题是,在用 JAVA 实现时, 是按算法模型建模,还是用对象模型建模呢? 如果用算法模型,那么 背包的值、重量就直接存入二个数组里;如果用对象模型,则要对背包以及背包问题进行对象建模。思来想去,还是采用了对象模型,尽管心里感觉算法模型似乎更好一些。有时确实就是这样,对象模型虽然现在很主流,但也不是万能的,采用其它的模型和视角,或许可以得到更好的解法。 背包建模: …0顶 79626浏览 2014-05-11 12:24:32分享
- 【输入文件】 输入的第1 行,为两个正整数,用一个空格隔开: N m; (其中N(<30000)表示总钱数,m(<25)为希望购买物品的个数。) 从第2 行到第m+1 行,第j 行给出了编号为j-1的物品的基本数据,每行有2 个非负整数 v p; (其中v 表示该物品的价格(v≤10000),p&n…0顶 68534浏览 2014-03-15 10:18:22分享
- 背包问题动态规划详解背包问题动态规划详解 ```{.cpp} /*任务: Sample Input 100 395 12030 3010 10 Sample Output 120 */ 代码实现: #include<stdio.h> #include<string…0顶 33968浏览 2013-03-29 15:39:35分享