int c;
int[] w;
int[] v;
Scanner scan=new Scanner(System.in);
System.out.print("输入背包的容量:");
c=scan.nextInt();
System.out.print("输入物品的数量:");
N=scan.nextInt();
System.out.print("分别输入物品的价值:");
v=new int[N];
for(int i=0;i<N;i++)
{
v[i]=scan.nextInt();
}
System.out.print("分别输入物品的重量:");
w=new int[N];
for(int i=0;i<N;i++)
int c;
int[] w;
int[] v;
Scanner scan=new Scanner(System.in);
System.out.print("输入背包的容量:");
c=scan.nextInt();
System.out.print("输入物品的数量:");
N=scan.nextInt();
}
}
for(int j = 0;j<N;j++)
totalx=totalx+n[j]*v[j];
ShowResult s = new ShowResult(v,w,N,n,totalx);
}
2.3、编程实现题目要求；
2.4、调试程序；
2.5、实验数据及实验结果；
输入数据：背包容量为50公斤。物品1重10公斤，价值60元；物品2重20公斤，价值100元；物品3重30公斤，价值120元。
for(int i= 0;i<N;i++)
for(int j=i+1;j<N;j++)
{
if(x[i] < x[j]){来自temp2 = x[j];
x[j] = x[i];
x[i] =temp2;
temp1 = v[j];
v[j] = v[i];
v[i] = temp1;
temp1 = w[j];
w[j] = w[i];
{
w[i]=scan.nextInt();
}
System.out.println();
int [] wCopy = new int [N];
int [] vCopy = new int [N];
float temp2;
int temp1;
float totalx=0;
float [] x = new float [N];//价值和重量的比值
}
}
for(int j = 0;j<N;j++)
totalx=totalx+n[j]*v[j];
ShowResult s = new ShowResult(v,w,N,n,totalx);
System.out.print("分别输入物品的价值:");
v=new int[N];
for(int i=0;i<N;i++)
{
v[i]=scan.nextInt();
}
System.out.print("分别输入物品的重量:");
w=new int[N];
for(int i=0;i<N;i++)
float [] n =new float[N];//记录个数
float [] nCopy = new float[N];
for(int i=0;i<N;i++)
{
wCopy [i] = w[i];
vCopy [i] = v[i];
}
for (int i=0;i<N;i++)
x[i] = (float) ((v[i]*1.0)/w[i]);
w[i] = temp1;
}
}//效益重量比值排序
Backpack b = new Backpack(c,w,v,n);
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{
if(wCopy[i]==w[j] && vCopy[i]==v[j])
{
nCopy[i] = b.n[i];
输出结果：
2.6、算法时间复杂度
O(nlogn)
三、总结
通过本次实验，加深了我对背包问题及贪心算法的理解。
附录：源代码
import java.util.Scanner;
import java.text.DecimalFormat;
public class greedbag
{
greedbag()
{
int N;
{
w[i]=scan.nextInt();
}
System.out.println();
int [] wCopy = new int [N];
int [] vCopy = new int [N];
float temp2;
int temp1;
float totalx=0;
float [] x = new float [N];//价值和重量的比值
float [] n =new float[N];//记录个数
float [] nCopy = new float[N];
for(int i=0;i<N;i++)
{
wCopy [i] = w[i];
vCopy [i] = v[i];
}
for (int i=0;i<N;i++)
x[i] = (float) ((v[i]*1.0)/w[i]);
《算法分析与设计》
课程实验
专业年级：信息与计算科学
学生学号：
学生姓名：
实验题目：用贪婪法求解背包问题
指导老师：
实验时间：20xx年xx月x日
一、实验内容
用贪婪法求解背包问题
要求：用非递归实现
二、实验步骤
2.1、理解算法思想和问题要求；
2.2、写出每个操作的算法
非递归算法：
greedbag()
{
int N;
w[i] = temp1;
}
}//效益重量比值排序
Backpack b = new Backpack(c,w,v,n);
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{
if(wCopy[i]==w[j] && vCopy[i]==v[j])
{
nCopy[i] = b.n[i];
for(int i= 0;i<N;i++)
for(int j=i+1;j<N;j++)
{
if(x[i] < x[j])
{
temp2 = x[j];
x[j] = x[i];
x[i] =temp2;
temp1 = v[j];
v[j] = v[i];
v[i] = temp1;
temp1 = w[j];
w[j] = w[i];