01背包问题有一个背包能装的重量maxw(正整数，0
编辑： admin 2017-27-02
-
4
去百度百科
类似问题
类似问题1：一个旅行者有一个最多能用M公斤的背包,现在有N件物品,第i件重量Wi,价值Pi.若每种物品只有一件 求旅行者能获得最大总价值for i=1...Nfor V=V...0f[v]=max{f[v],f[v-w[i]]+p[i]}为什么V要递减[数学科目]
这个是状态转移方程
f[v] 表示背包剩余容量V时候积累的价值总和
你这个是优化版本的只用了一维数组 有个更基本的方法我解释给你听
有n件物品 假设当前到第i件了
{ f[i - 1][v];
f[i][v](到第i件时 此时容量为v ) = {
{ f[i - 1][v - w[i]] + p[i];（v>=w[i]）
(两者中较大的那个)
“将前i件物品放入容量为v的背包中”这个子问题,若只考虑第i件物品的策略（放或不放）,那么就可以转化为一个只牵扯前i-1件物品的问题.如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为v的背包中”,价值为f[i-1][v]；如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”,此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i].
类似问题2：01连续背包问题.1．考虑而不是xi∈{0,1}的连续背包问题.一种可行的贪婪策略是：按价值密度递减的顺序检查物品,若剩余容量能容下正在考察的物品,将其装入；否则,往背包内装该物品的一部
这个对你应该有用
/*
标题：应试编程实例-[分治法程序设计]
作者：成晓旭
时间：2002年09月18日(21:43:00-22:03:00)
实现“快速排序算法”问题的分而治之算法函数
*/
#include "stdio.h"
#include "stdlib.h"
//:
int main(int argc,char* argv[])
{
Run_Quick_Sort();
printf("\n应用程序运行结束!\n");
return 0;
}
类似问题3：01背包问题（变形）有一个箱子容量为v(正整数,o≤v≤20000),同时有n个物品(o≤n≤30),每个物品有一个体积 (正整数).要求从 n 个物品中,任取若干个装入箱内,使箱子的剩余空间为最小.输入第一
建议你看看锁具分配的算法设计问题.一般的算法设计书上都有这个讲解,例子很像,你试试.
类似问题4：动态规划的01背包问题,来自背包九讲上的一段：-------------------------------------------------------------------------------------------------------有N件物品和一个容量为V的背包.第i件物品的费用是c[i],价值是w[i[数学科目]
注意到原来每次f[i][v]只用了一次,所以现在f[v]相当于原来的f[v],
上次循环保存的f[v]相当于原来的f[i-1][v]
如果从0做到V的话,没有重复限制,会从v->v+c[i]->v+2*c[i]加上去,本次循环的c[i]也会加上