01背包问题的Golang和Matlab代码

不得不说，Matlab在处理数据方面实在显得太强大了，往往通过Matlab内置函数一行搞定的代码，在Go语言和Python中需要好几行，甚至需要自己写函数。

例：有10件货物要从甲地运往乙地，每件货物的重量（单位：吨）和利润（单位：元），如下表所示

由于只有一辆最大载重为30t的货车能用来运送货物，所以只能选择部分货物配送，要求确定运送货哪些货物，使得运送这些货物的总利润最大。

Matlab代码

function [f,IND] = knapsack01problem1(p,w,W)
    m = length(p);
    FF = zeros(m,W);
    if w(1)<=W   % 初始化第一行
        FF(1,w(1):end)=p(1);
    end
    for i=2:m   % 初始化第一列
        FF(i,1)=max([p(w(1:i)==1),0]); % 找出当前位置等于1的最大价值量
    end
    for i=2:m
        for j=2:W
            if w(i)>j
                FF(i,j)=FF(i-1,j);
            elseif w(i)==j
                FF(i,j)=max(FF(i-1,j),p(i));
            else
                FF(i,j)=max(FF(i-1,j),p(i)+FF(i-1,j-w(i)));

            end
        end
    end
    f = FF(m,W);

    IND = [];
    ww = W;  % 初始化背包的剩余容量为W
    tmp=FF(:,ww); % 取出最后一列
    while 1
        ind = find(tmp==max(tmp),1); % 取出当前背包中第一个最大价值对应的物品
        ww = ww-w(ind);
        IND = [IND ind];
        if ind>1 && ww>0  % 当取出一个物品后，背包容量为0结束；索引=1后结束
            tmp=FF(1:ind-1,ww);
        else
            break
        end
    end
    IND = sort(IND);

end

• 输入： p = [540 200 180 350 60 150 280 450 320 120]; w = [6 3 4 5 1 2
  3 5 4 2]; W = 30; [f,IND]=knapsack01problem1(p,w,W)
• 输出： f = 2410
  IND = 1 2 4 6 7 8 9 10

Go代码

// @author:来瓶安慕嘻
// @time:2020-11-06 20:39:16
// @file:main.go
// @开始美好的一天吧 ('μ')

package main

import (
	"fmt"
	"sort"
)

func knapsack01problem(p,w []int,W int)(int,[][]int){
	m := len(p)
	// 初始化FF数组
	FF := make([][]int,m)
	for i:=0;i<m;i++{
		for j:=0;j<W;j++{
			FF[i] = append(FF[i], 0)
		}
	}
	// 初始化第一行
	if w[0]<W{
		for i:=w[0];i<=W;i++{
			FF[0][i-1]=p[0]
		}
	}

	// 初始化第一列
	for i:=1;i<m;i++{
		var tmp []int
		if w[i]==0{
			tmp = append(tmp,p[i])
		}
		sort.Ints(tmp)
		if len(tmp) != 0{
			FF[i][0] = tmp[len(tmp)-1]
		}else {
			FF[i][0] = 0
		}

	}


	for i:=1;i<m;i++{
		for j:=1;j<W;j++{
			if w[i]>j+1{
				FF[i][j]=FF[i-1][j]
			}else if w[i]==j+1{
				FF[i][j]= max(FF[i-1][j],p[i])
			}else if w[i]<j+1 {
				FF[i][j] = max(FF[i-1][j],p[i]+FF[i-1][j-w[i]])
			}
		}
	}
	return FF[m-1][W-1],FF
}

func find_ind(FF [][]int,w []int,W int)[]int  {
	var IND []int
	tmp := make([]int,len(FF))
	ww := W-1
	for i:=0;i<len(FF);i++{
		tmp[i] = FF[i][len(FF[1])-1]  // 取出最后一列
	}
	//fmt.Println(tmp)

	for{
		tmp1 := tmp
		sort.Ints(tmp)
		ind := find_index(tmp1,tmp[len(tmp1)-1])
		ww = ww-w[ind]
		IND = append(IND, ind)
		if ind>0 && ww>0{
			tmp = make([]int,ind)
			for j:=0;j<(ind);j++{
				tmp[j] = FF[j][ww]
			}
		} else {
			break
		}
	}
	sort.Ints(IND)
	return IND
}



func max(x,y int)int{
	if x>y{
		return x
	}
	return y
}

func find_index(X []int,des int)int{
	for k,v:=range X{
		if v==des{
			return k
		}
	}
	return 0
}

• 输入： func main() { p := []int{540,200,180,350,60,150,280,450,320,120} w :=
  []int{6,3,4,5,1,2,3,5,4,2} W := 30 ret,FF :=
  knapsack01problem(p,w,W) fmt.Printf(“最大的价值为:%v n”,ret)

  ret2 := find_ind(FF,w,W) fmt.Printf(“选择了:%v n”,ret2) // 1 2 4 6 7 8
  9 10 }

• 输出： 最大的价值为:2410
  选择了:[0 1 3 5 6 7 8 9]

最后

以上就是端庄早晨为你收集整理的01背包问题的Golang和Matlab代码的全部内容，希望文章能够帮你解决01背包问题的Golang和Matlab代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。