该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
0-1背包问题，java的动态规划
如题，代码如下
public class dongtaiguihua01
{
public static void main(String []args)
{
int W=10;//背包的总重量
int []w= {2,2,6,5,4};//物品的相应重量
int []v= {6,3,5,4,6};//物品的相应价值
int [][]value=new int [5][11];
int []num= new int [4];
for(int i=0;i<5;i++)
{
for(int j=0;j<11;j++)
{
if(i==0||j==0)
{
value[i][j]=0; //第一种情况
}
else if(w[i]>j)
{
value[i][j]=value[i-1][j];//第二种情况
}
else if(i>0&&w[i]<=j)//第三种情况
{
int num1,num2;
num1=value[i-1][j-w[i]]+v[i];//放入后的价值
num2=value[i-1][j];//没有放入的价值
if(num1>num2)
{
value[i][j]=num1;
}
else
{
value[i][j]=num2;
}
}
}
}
//已经求出最大的价值，并且已经知道最后一个元素是否放入包中
for(int i=3;i>=0;i--)
{
if(value[i+1][W]!=value[i][W])
{
num[i]=1;
W=W-w[i+1];
}
else {
num[i]=0;
}
}
System.out.println("放入包中的物品为：");
for(int i=0;i<4;i++)
{
if(num[i]==1)
{
System.out.println("质量为："+w[i+1]+",价值为："+v[i+1]);
}
}
System.out.println("最大的价值为："+value[4][10]);
}
}
#吴世勋朴灿烈合作新专辑##吴世勋朴灿烈合作新专辑#
