算法分析与设计题目 请求解012背包问题：有1个背包...

精选知识

(1) m(i,j)=max( m(i-1,j-w[i])+v[i] , m(i-1,j) , m(i-1,j-2*w[i])+2*v[i] );

(2)

for (int i=0;i<=n;i++)
for (int j=0;j<=c;j++) m[i][j]=-10000;
m[0][0]=0;
for (int i=1;i<=n;i++)
for (int j=0;j<=c;j++)
{
m[i][j]=max(m[i][j],m[i-1][j]);
if (j+w[i]<=c) m[i][j+w[i]]=max(m[i][j+w[i]],m[i-1][j]+v[i]);
if (j+2*w[i]<=c) m[i][j+2*w[i]]=max(m[i][j+2*w[i]]+2*v[i]);
}

(3)

取 2个 第二种物品,2个 第三种物品,获得价值最大为70

其他类似问题

问题1：关于算法分析与设计的题目试列举比较常见的阶分别为O(n2)和O(nlogn) 的排序算法.①：由阶O(n2)改进为阶O(nlogn)的根本原因是什么?②：快速排序算法、归并排序算法、堆排序算法三者之间有什[数学科目]

基本没人回答?

问题2：算法分析与设计一、编程题(Programming problem)(20分)编写冒泡排序算法public static int[] BullerSort(int a[]),并验证该算法的正确性.Java项目名称为ks01,类为ks01.二、编程题(Programming problem) (20分)已知a数

老师看着呢0.o

问题3：算法分析与设计的题 最大值和次大值问题的最优算法要求算法时间复杂度n+logn-2

这个O(n)就够了吧

线性扫描两次

问题4：一道算法分析与设计的题,假设有7个物品,它们的重量和价值如下表所示.若这些物品均可以被分割,且背包容量M＝140,使用贪心算法求解此背包问题.W（35,30,50,60,40,10,25）p（10,40,30,50,35,40,30）[数学科目]

背包问题,看黑书的时候做过一个练习,可在我的空间“结构算法”分类下找到.

其中包含完整的代码.有问题欢迎交流啊

问题5：现在学习算法分析与设计,遇到两道题难题,先谢谢您了：一、有n(n为偶数)个互不相同的正整数,将其分成个数相同的两部份,后一部份比前一部份大,用线性时间完成.（1）写出其数据结构（2）[数学科目]

1:快排,O(n)

2:二分图的匹配 看用什么算法 匈牙利算法 邻接矩阵O(n^3)或邻接表0(m*n)