问题描述(引用算法导论描述):给定一段长度为n英寸的钢条(一个整型)和一个价格表p(一个数组)求钢条最优切割方案,使得销售的收益最大,如果n英寸的钢条的价格p[n]足够大,那么钢条有可能不需要切割
Java版本
原始版:
//原始求解方法
/**
*
* @param p 价格数组
* @param n 钢条长度
* @return 最优的价格
*/
public int primaryCut(int[] p,int n){
if(n == 0){
return 0;
}
int q = Integer.MIN_VALUE;
for (int i = 1; i <= n; i++) {
q = Math.max(q,p[i] + primaryCut(p,n-i));
}
return q;
}
//备忘录求解方法
//使用散列表记录整个备忘录
public int memoryCut(int[] p,int n){
int[] memory = new int[n+1];
for (int i = 0; i < memory.length; i++) {
memory[i] = Integer.MIN_VALUE;
}
return memoryCutAux(p,n,memory);
}
public int memoryCutAux(int[] p,int n,int[] memory){
if (memory[n] > 0){
return memory[n];
}
if(n == 0){
return 0;
}
int q = Integer.MIN_VALUE;
for (int i = 1; i <= n; i++) {
q = Math.max(q,p[i] + memoryCutAux(p,n-i,memory));
}
memory[n] = q;
return memory[n];
}
//自底向上方法求解
public int BottomUpmemoryCut(int[] p,int n){
int[] r = new int[n+1];
r[0] = 0;
for (int i = 1; i <= n; i++) {
int q = Integer.MIN_VALUE;
for (int j = 1; j <= i; j++) {
q = Math.max(q,p[j] + r[i-j]);
}
r[i] = q;
}
return r[n];
}
Python版本:
#原始求解方法
def primary_cut(p,n):
if n == 0:
return 0;
q = -10000
for i in range(1,n+1):
q = max(q,p[i] + primary_cut(p,n-i))
return q
#记忆数组求解方法
def memory_cut(p,n):
r = [-1 for i in range(n+1)]
return memory_cut_aux(p,n,r)
def memory_cut_aux(p,n,r):
if r[n] > 0 :
return r[n]
if n == 0:
return 0
else :
q = -1
for i in range(1,n+1):
q = max(q,p[i] + memory_cut_aux(p,n-i,r))
r[n] = q
return r[n]
#自底向上求解方法
def buttom_up_memory_cut(p,n):
r = [-1 for i in range(n+1)]
r[0] = 0
for i in range(1,n+1):
q = -1
for j in range(1,i+1):
q = max(q,p[j] +r[i - j])
r[i] = q
return r[n]
Golang版本:
//primary
func primaryCut(p []int, n int) int {
if n == 0 {
return 0
}
q := -1
for i := 1; i <= n; i++ {
q = max(q, p[i]+primaryCut(p, n-i))
}
return q
}
//记忆数组
func memoryCut(p []int, n int) int {
r := []int{}
for i := 0; i <= n; i++ {
r = append(r, -1)
}
return memoryCutAux(p, n, r)
}
func memoryCutAux(p []int, n int, r []int) int {
if r[n] > 0 {
return r[n]
}
if n == 0 {
return 0
}
q := -1
for i := 1; i <= n; i++ {
q = max(q, p[i]+memoryCutAux(p, n-i, r))
}
r[n] = q
return r[n]
}
//自底向下
func bottomUpMemory(p []int, n int) int {
r := []int{}
for i := 0; i <= n; i++ {
r = append(r, -1)
}
r[0] = 0
for i := 1; i <= n; i++ {
q := -1
for j := 1; j <= i; j++ {
q = max(q, p[j]+r[i-j])
}
r[i] = q
}
return r[n]
}