网站建设计划设计方案,360建筑网发的消息怎么取消,宁德市,商标注册查询怎么查询01背包问题#xff1a; 1.递归思想 0- 1 背包问题如果采用递归算法来描述则非常清楚明白, 它的算法根本思想是假设用布尔函数knap( s, n) 表示n 件物品放入可容质量为s 的背包中是否有解( 当knap 函数的值为真时 说明问题有解,其值为假时无解) . 我们可以通过输入s 和n 的值, …01背包问题 1.递归思想 0- 1 背包问题如果采用递归算法来描述则非常清楚明白, 它的算法根本思想是假设用布尔函数knap( s, n) 表示n 件物品放入可容质量为s 的背包中是否有解( 当knap 函数的值为真时 说明问题有解,其值为假时无解) . 我们可以通过输入s 和n 的值, 根据它们的值可分为以下几种情况讨论: ( 1) 当s 0时可知问题有解, 即函数knap( s, n) 的值为true; ( 2) 当s 0 时这时不可能, 所以函数值为false; ( 3) 当输入的s 0 且n 1 时即总物品的件数不足1, 这时函数值为false, 只有s 0 且n \1 时才符合实际情况,这时又分为两种情况: ( 1) 选择的一组物体中不包括Wn 则knap( s, n) 的解就是knap( s, n- 1) 的解. ( 2) 选择的一组物体中包括Wn 则knap( s, n) 的解 就是knap( s- Wn, n- 1) 的解. 这样一组Wn 的值就是问题的最佳解. 这样就将规模为n 的问题转化为 规模为n- 1 的问题. 综上所述0- 1 背包问题的递归函数定义为:knap( s, n) ∕true, s 0 ︳false, s 0 ︳false, s 0 且n 1 \knap( s, n- 1) 或knap( s- Wn, n- 1) , s 0 且n 1采用此法求解0- 1 背包问题的时间复杂度为O( n) . 上述算法对于所有物品中的某几件恰能装满背包时能准确求出最佳解. 但一般情况是对于某一些物品无论怎么装都不能装满背包, 必须要按背包的最大容量来装. 如物品件数为4, 其质量分别为: 10, 2, 5, 4, 背包的容量为20, 则这四件物品无论怎么放都不能恰好装满背包, 但应能最大限度装, 即必须装下10, 5, 4 这三件物品, 这样就能得到最大质量19. 对于这种装不满的背包它的解决办法是这样的: 按所有物品的组合质量最大的方法装背包, 如果还装不满,则我们可以考虑剩余空间能否装下所有物品中最小的那件, 如果连最小的都装不下了则说明这样得到的解是最佳解, 问题解决. 这样我们必须先找出所有n 件物品中质量最小的那件( 它的质量为Min) , 但是为了问题的解决我们不能增加运算次数太多, 并且必须运用上述递归函数. 那么我们可通过修改s 的值即背包的容量, 从背包容量s 中减去k( 它的值是从0 到Min- 1 之间的一个整数值) , 再调用递归函数. 当k 0 时即能装满背包, 其它值也能保证背包能最大限度装满, 这样所有问题都解决了. ①例题一 简单背包问题Time Limit: 1000MS Memory Limit: 65535KB Submissions: 2217 Accepted: 408 Description 设有一个背包可以放入的物品重量为S现有n件物品重量分别是w1w2w3…wn。 问能否从这n件物品中选择若干件放入背包中使得放入的重量之和正好为S。 如果有满足条件的选择则此背包有解否则此背包问题无解。 Input输入数据有多行包括放入的物品重量为s物品的件数n以及每件物品的重量输入数据均为正整数多组测试数据。 Output对于每个测试实例若满足条件则输出“YES”若不满足则输出“NO“ Sample Input20 51 3 5 7 9Sample OutputYES # includestdio.h
# includestring.h
int date[1005];
int f(int w,int s)
{if(w0) return 1;//正好if(w0||w0 s0) return 0;if(f(w-date[s],s-1)) return 1;//退出来再选下一个 return f(w,s-1);//选择下一个
}int main()
{int i,Weight,n;while(scanf(%d %d,Weight,n)!EOF){memset(date,0,sizeof(date));for(i1;in;i)scanf(%d,date[i]);if(f(Weight,n))printf(YES\n);else printf(NO\n);}return 0;
}
} 2.贪心算法 用贪心法设计算法的特点是一步一步地进行根据某个优化测度可能是目标函数也可能不是目标函数每一步上都要保证能获得局部最优解。 每一步只考虑一个数据它的选取应满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时就不把该数据添加到部分解中 直到把所有数据枚举完或者不能再添加为止。 #includeiostream
#includealgorithm
using namespace std;
struct good//表示物品的结构体
{double p;//价值double w;//重量double r;//价值与重量的比
};
good a[2000];
bool bigger(good a,good b)
{if(a.rb.r)return a.wb.w;else return a.rb.r;
}
int main()
{
double s,value,m;
int i,n;cinmn;//读入包的容量和物品个数for (i0;in;i){cina[i].wa[i].p;a[i].ra[i].p/a[i].w;}sort(a,an,bigger);//调用sort排序函数按照价值与重量比和质量排序贪心s0;//包内现存货品的重量value0;//包内现存货品总价值for (i0;in;i)if(sa[i].wm){valuea[i].p;sa[i].w;}
coutThe total value is valueendl;//输出结果return 0;
} 但仔细想就会发现有个很大的问题10 45 108 165 510 10就会出问题被装进去就不会拿出来可见“拿来主义”行不通接下来介绍另一种算法动规 3.动态规划【正解】 有N件物品和一个容量为V的背包。第i件物品的体积是c[i]价值是w[i]。求解将哪些物品装入背包可使价值总和最大。状态转移方程f[i][v]max{f[i-1][v],f[i-1][v-c[i]]w[i]} 这个方程非常重要基本上所有跟背包相关的问题的方程都是由它衍生出来的 伪码 for i1..N for vV..0 f[v]max{f[v],f[v-c[i]]w[i]};如果不放第i件物品那么问题就转化为“前i-1件物品放入容量为v的背包中”价值为f[i-1][v]如果放第i件物品那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。 ②例题二采药 Time Limit: 1000MS Memory Limit: 65535KB Submissions: 155 Accepted: 50 Description辰辰是个天资聪颖的孩子他的梦想是成为世界上最伟大的医师。为此他想拜附近最有威望的医师为师。医师为了判断他的资质给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说“孩子这个山洞里有一些不同的草药采每一株都需要一些时间每一株也有它自身的价值。我会给你一段时间在这段时间里你可以采到一些草药。如果你是一个聪明的孩子你应该可以让采到的草药的总价值最大。”如果你是辰辰你能完成这个任务吗 Input输入的第一行有两个整数T1 T 1000和M1 M 100用一个空格隔开T代表总共能够用来采药的时间M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间包括1和100的整数分别表示采摘某株草药的时间和这株草药的价值。 Output输出包括一行这一行只包含一个整数表示在规定的时间内可以采到的草药的最大总价值。 Sample Input70 371 10069 11 2Sample Output3 #includeiostream
# includecstring
# define max(a,b) ab?a:b
using namespace std;
int main()
{int dp[101][1001],m,T,w[101],val[101],i,j;cinTm;for(i1;im;i)cinw[i]val[i];memset(dp,0,sizeof(dp));for(i1;im;i)for(j0;jT;j)//j相当于上面说的V-c[i]{if(jw[i])dp[i][j]max(dp[i-1][j],dp[i-1][j-w[i]]val[i]);//放还是不放的选择else dp[i][j]dp[i-1][j];}coutdp[m][T]endl;return 0;
} 这里就测试一下10 45 108 165 510 10 转载于:https://www.cnblogs.com/GoAhead/archive/2012/11/02/2751486.html
