0-1背包算法和完全背包算法MATLAB代码实现

本文主要是介绍0-1背包算法和完全背包算法MATLAB代码实现，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

有10件物品，它们的重量分别是5,8,3,2,6,6,5,4,7,5,，它们的价值分别是2,4,7,7,3,6,3,5,4,6，现在给你个承重为30的背包，试用0-1背包、完全背包算法，分别计算如何让背包里装入的物品具有最大的价值总和？

0-1背包算法

clear all
clc
close all
v=[2,4,7,7,3,6,3,5,4,6];%物品价值
w=[5,8,3,2,6,6,5,4,7,5];%物品重量
m=zeros(10,31);%建立二维数组
for j=0:30
    if j>=w(1)
        m(1,j+1)=v(1);
    end
end%初始化第一行，数组编码从1开始，因此下标要加1
for i=2:10
    for j=1:30
        if j>=w(i)%背包可以装下当前物体
            m(i,j+1)=max(m(i-1,j+1),m(i-1,j-w(i)+1)+v(i));%1.不装 2.空出刚好可以放进去的容量
        else
            m(i,j+1)=m(i-1,j+1);%容量不够不能装
        end
    end
end
disp(m(10,31))

矩阵最后一个元素即为价值最大值

完全背包算法

clear all
clc
close all
v=[2,4,7,7,3,6,3,5,4,6];%物品价值
w=[5,8,3,2,6,6,5,4,7,5];%物品重量
m=zeros(10,31);%建立二维数组
for j=1:31
     m(1,j)=floor(j/w(1))*v(1);
end %初始化第一行，数组编码从1开始，因此下标要加1
for i=2:10
    for j=1:30
        for k=1:floor(j/w(i))%最多可以取k个背包
                 m(i,j+1)=max(m(i,j+1),m(i-1,j-k*w(i)+1)+k*v(i));%1、不取，2、取k个i背包
        end
    end
end
disp(m(10,31))

这篇关于0-1背包算法和完全背包算法MATLAB代码实现的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！