- 基本思路： 这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。 用子问题定义状态：即f[v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则 其状态转移方程便是：f[v]=max{f[v],f[v-c]+w}。 实现代码： …0顶 290浏览 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顶 456浏览 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顶 338浏览 2014-09-18 10:43:17分享
- 基本思路： 这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。 用子问题定义状态：即f[v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则 其状态转移方程便是：f[v]=max{f[v],f[v-c]+w}。 实现代码： …0顶 54746浏览 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顶 81953浏览 2014-09-10 10:57:23分享
- 值得提及的一个问题是，在用 JAVA 实现时， 是按算法模型建模，还是用对象模型建模呢？ 如果用算法模型，那么 背包的值、重量就直接存入二个数组里；如果用对象模型，则要对背包以及背包问题进行对象建模。思来想去，还是采用了对象模型，尽管心里感觉算法模型似乎更好一些。有时确实就是这样，对象模型虽然现在很主流，但也不是万能的，采用其它的模型和视角，或许可以得到更好的解法。 背包建模： …0顶 28024浏览 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顶 28120浏览 2014-08-03 12:27:04分享
- 假如有物品如下： 物品号 物品名 重量 价钱 0 李子 4 4500 1 苹果 5 …0顶 84301浏览 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顶 70670浏览 2014-07-24 15:34:15分享
- 值得提及的一个问题是，在用 JAVA 实现时， 是按算法模型建模，还是用对象模型建模呢？ 如果用算法模型，那么 背包的值、重量就直接存入二个数组里；如果用对象模型，则要对背包以及背包问题进行对象建模。思来想去，还是采用了对象模型，尽管心里感觉算法模型似乎更好一些。有时确实就是这样，对象模型虽然现在很主流，但也不是万能的，采用其它的模型和视角，或许可以得到更好的解法。 背包建模： …0顶 89300浏览 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顶 76545浏览 2014-03-15 10:18:22分享
- 背包问题动态规划详解背包问题动态规划详解 ```{.cpp} /*任务： Sample Input 100 395 12030 3010 10 Sample Output 120 */ 代码实现： #include<stdio.h> #include<string…0顶 37181浏览 2013-03-29 15:39:35分享
