实验一 算法实现一
一、 实验目的与要求
熟悉C/C++语言的集成开发环境；
通过本实验加深对分治法、贪心算法的理解。
二、 实验内容:
掌握分治法、贪心算法的概念和基本思想，并结合具体的问题学习如何用相应策略进行求解的方法。
三、 实验题
1. 【伪造硬币问题】给你一个装有n个硬币的袋子。n个硬币中有一个是伪造的。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。试用分治法的思想写出解决问题的算法，并计算其时间复杂度。
import java.util.Scanner;
import java.io.*;
publicclass coin {
publicstaticint Compare(int [] coin ,int astart,int bstart,int n)
{
int i,asum=0,bsum=0;
for(i=astart;i<astart+n;i++) //astart 前一个分组的开始；bstart 后一个分组的开始；n 每个分组的长度
asum+=coin[i];
for(i=bstart;i<bstart+n;i++)
bsum+=coin[i];
if(asum<bsum)
return -1;
elseif(asum==bsum)
return 0;
else
return 1;
}
publicstaticint Find(int coin[] ,int start,int n)
{
if(n==1)
{
System.out.print("假硬币的位置是：");
return start;
}
elseif((n%2)==0)
{
if(Compare(coin,start,n/2,n/2)==-1)
return Find(coin,start,n/2);
elseif(Compare(coin,start,n/2,n/2)==0)
return -1;
else
return Find(coin,n/2,n/2);
}
else
{
if(Compare(coin,start,start+(n-1)/2,(n-1)/2)==-1)
return Find(coin,start,(n-1)/2);
elseif(Compare(coin,start,start+(n-1)/2,(n-1)/2)==0)
return Find(coin,start+n-1,1);
else
return Find(coin,start+(n-1)/2,(n-1)/2);
}
}
publicstaticvoid main(String[] args) throws IOException
{
int n;
Scanner input = new Scanner (System.in);
System.out.println("请输入硬币总数n:");
n=input.nextInt();
int coin[] = newint[n+1];
int i,j;
for(i=1;i<=n;i++)
coin[i]=1;
j=(int)(Math.random()*n); //生成一随机数，来存放假币
coin[j+1]=0;
for(i=1;i<=n;i++)
System.out.print(" "+coin[i]);
System.out.print("\n");
System.out.print(" "+Find(coin,1,n));
}
2. }
2.【找零钱问题】一个小孩买了价值为33美分的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目有限的面值为25美分、10美分、5美分、及1美分的硬币。给出一种找零钱的贪心算法。
import java.util.Scanner;
import java.io.*;
publicclass zhaoqian {
publicstaticvoid main(String[] args) throws IOException
{
int i,n,m,k,d,money=33;
int count25=0;int count10=0;
int count5=0;int count1=0;
Scanner input = new Scanner (System.in);
System.out.println("请输入拥有的25美分的数目n:");
n=input.nextInt();
int coin[] = newint[100];
for(i=0;i<n;i++)
coin[i]=25;
System.out.println("请输入拥有的10美分的数目m:");
Scanner input1 = new Scanner (System.in);
m=input1.nextInt();
for(i=n;i<n+m;i++)
coin[i]=10;
System.out.println("请输入拥有的5美分的数目k:");
Scanner input2 = new Scanner (System.in);
k=input2.nextInt();
for(i=n+m;i<n+m+k;i++)
coin[i]=5;
System.out.println("请输入拥有的1美分的数目d:");
Scanner input3 = new Scanner (System.in);
d=input3.nextInt();
for(i=n+m+k;i<n+m+k+d;i++)
coin[i]=1;
for(i=0;i<n+m+k+d;i++)
System.out.print(" "+coin[i]);
System.out.print("\n");
while((money-=25)>=0&&n>0)
count25++;
money+=25;
while((money-=10)>=0&&m>0)
count10++;
money+=10;
while((money-=5)>=0&&k>0)
count5++;
money+=5;
while((money-=1)>=0&&d>0)
count1++;
money+=1;
if(25*count25+10*count10+5*count5+1*count1<33)
System.out.println("不好意思，零钱找不开！");
else
{
System.out.println("所需要找的25美分的个数为:"+count25);
System.out.println("所需要找的10美分的个数为:"+count10);
System.out.println("所需要找的5美分的个数为:"+count5);
System.out.println("所需要找的1美分的个数为:"+count1);
}
}
}
实验二 算法实现二
一、 实验目的与要求
熟悉C/C++语言的集成开发环境；
通过本实验加深对贪心算法、动态规划和回溯算法的理解。
二、 实验内容:
掌握贪心算法、动态规划和回溯算法的概念和基本思想，分析并掌握"0-1"背包问题的三种算法，并分析其优缺点。
三、 实验题
1. "0-1"背包问题的贪心算法
import java.util.*;
publicclass beibao
{
double[] zhongliang;
double[] jiaqian;
int[] wupin;
int s,h;
double w;
publicvoid input()
{
System.out.println("请输入物品个数");
Scanner reader=new Scanner(System.in);
s=reader.nextInt();
zhongliang=newdouble[s];
jiaqian=newdouble[s];
wupin=newint[s];
System.out.println("请输入包的成重量");
Scanner reade=new Scanner(System.in);
w=reade.nextDouble();
for(int i=0;i<s;i++)
{
System.out.println("请输入第"+(i+1)+"物品重量");
Scanner readers=new Scanner(System.in);
double a=readers.nextDouble();
zhongliang[i]=a;
System.out.println("请输入第"+(i+1)+"物品总价格");
Scanner readerss=new Scanner(System.in);
double b=readerss.nextDouble();
jiaqian[i]=b/a;
wupin[i]=i;
}
}
publicvoid sort()
{
double c=0.0d;
double d=100.0d;
for(int i=0;i<s;i++)
{
for(int j=0;j<s;j++)
{
if(jiaqian[j]>c&&jiaqian[j]<d)
{
c=jiaqian[j];
h=j;
}
}
wupin[i]=h;
d=c;
c=0.0d;
}
}
publicvoid tests()
{
sort();
int x=0;
for(int i=0;i<s;i++)
{
if(zhongliang[wupin[i]]>w)
break;
w-=zhongliang[wupin[i]];
System.out.println("可装入第"+(wupin[i]+1)+"物品");
x=i+1;
}
if(x<=(s-1))
{
System.out.println("可装入第"+(wupin[x]+1)+"物品的"+(w/zhongliang[wupin[x]]));
}
}
}
class test
{
publicstaticvoid main(String[] args)
{
beibao baos=new beibao();
baos.input();
baos.tests();
}
}
2."0-1"背包问题的动态规划算法
import java.util.ArrayList;
import java.util.*;
publicclass Knapsack
{
privateint weight;
privateint value;
public Knapsack(int weight, int value)
{
this.value = value;
this.weight = weight;
}
publicint getWeight()
{
return weight;
}
publicvoid setWeight(int weight)
{
this.weight = weight;
}
publicint getValue()
{
return value;
}
publicvoid setValue(int value)
{
this.value = value;
}
public String toString()
{
return "[weight: " + weight + " " + "value: " + value + "]";
}
}
class KnapsackProblem
{
private Knapsack[] bags;
privateint totalWeight;
privateint n;
privateint[][] bestValues;
privateint bestValue;
private ArrayList bestSolution;
public KnapsackProblem(Knapsack[] bags, int totalWeight, int n)
{
this.bags = bags;
this.totalWeight = totalWeight;
this.n = n;
if (bestValues == null)
{
bestValues = newint[n+1][totalWeight+1];
}
if (bestSolution == null)
bestSolution = new ArrayList();
}
publicvoid solution()
{
System.out.println("所给定物品为：");
for(Knapsack b: bags)
{
System.out.println(b);
}
System.out.println("所要求总承重为: " + totalWeight);
// 求解最优值
for (int j = 0; j <= totalWeight; j++)
{
for (int i = 0; i <= n; i++)
{
if (i == 0 || j == 0)
{
bestValues[i][j] = 0;
}
else
{
if (j < bags[i-1].getWeight())
{
bestValues[i][j] = bestValues[i-1][j];
}
else
{
int iweight = bags[i-1].getWeight();
int ivalue = bags[i-1].getValue();
bestValues[i][j] = Math.max(bestValues[i-1][j], ivalue + bestValues[i-1][j-iweight]);
}
}
}
}
// 求解背包组成
int tempWeight = totalWeight;
for (int i=n; i >= 1; i--)
{
if (bestValues[i][tempWeight] > bestValues[i-1][tempWeight])
{
bestSolution.add(bags[i-1]);
tempWeight = totalWeight - bags[i-1].getWeight();
}
}
}
publicint getBestValue()
{
bestValue = bestValues[n][totalWeight];
return bestValue;
}
publicint[][] getBestValues()
{
return bestValues;
}
publicArrayList getBestSolution()
{
return bestSolution;
}
}
class TestKnapsack
{
publicstaticvoid main(String[] args)
{
System.out.println("请输入物品个数");
Scanner reader=new Scanner(System.in);
int s=reader.nextInt();
int jiage[]=newint[s];
int zhongliang[]=newint[s];
System.out.println("请输入包的成重量");
Scanner reade=new Scanner(System.in);
int totalWeight = reade.nextInt();
for(int i=0;i<s;i++)
{
System.out.println("请输入第"+(i+1)+"物品重量");
Scanner readers=new Scanner(System.in);
zhongliang[i]=readers.nextInt();
System.out.println("请输入第"+(i+1)+"物品总价格");
Scanner readerss=new Scanner(System.in);
jiage[i]=readerss.nextInt();
}
Knapsack[] bags = new Knapsack[]
{
new Knapsack(zhongliang[0],jiage[0]),
new Knapsack(zhongliang[1],jiage[1]),
new Knapsack(zhongliang[2],jiage[2]),
new Knapsack(zhongliang[3],jiage[3])
};
int n = bags.length;
KnapsackProblem kp = new KnapsackProblem(bags, totalWeight, n);
kp.solution();
System.out.println("最优值为：" + kp.getBestValue());
System.out.println("最优解——选取的背包为: ");
System.out.println(kp.getBestSolution());
System.out.println("最优值矩阵");
int[][] bestValues = kp.getBestValues();
for (int i=0; i < bestValues.length; i++)
{
for (int j=0; j < bestValues[i].length; j++)
{
System.out.printf("%-5d", bestValues[i][j]);
}
System.out.println();
}
}
}
3."0-1"背包问题的回溯算法
import java.util.*;
publicclass Knapsack
{
privatedouble[] p,w;//分别代表价值和重量
privateint n;
privatedouble c,bestp,cp,cw;
privateint x[]; //记录可选的物品
privateint[] cx;
public Knapsack(double pp[],double zhongliang[],double jiage){
this.p=pp;this.w=zhongliang;this.n=pp.length-1;
this.c=jiage;this.cp=0;this.cw=0;
this.bestp=0;
x=newint[zhongliang.length];
cx=newint[pp.length];
}
void knapsack(){
backtrack(0);
}
void backtrack(int i){
if(i>n){ //判断是否到达了叶子节点
if(cp>bestp){
for(int j=0;j<x.length;j++)
x[j]=cx[j];
bestp=cp;
}
return;
}
if(cw+w[i]<=c){//搜索右子树
cx[i]=1;
cw+=w[i];
cp+=p[i];
backtrack(i+1);
cw-=w[i];
cp-=p[i];
}
cx[i]=0;
backtrack(i+1); //检查左子树
}
void printResult(){
System.out.println("回溯法");
System.out.println("物品个数：n=5");
System.out.println("背包容量：c=10");
System.out.println("物品重量数组：zhongliang= {2,2,6,5,4}");
System.out.println("物品价值数组：jiage= {6,3,5,4,6}");
System.out.println("最优值：="+bestp);
System.out.println("选中的物品是:");
for(int i=0;i<x.length;i++){
System.out.print(x[i]+" ");
}
}
publicstaticvoid main(String[] args){
double p[]={6,3,5,4,6};
double w[]={2,2,6,5,4};
int maxweight=10;
Knapsack ks=new Knapsack(p,w,maxweight);
ks.knapsack(); //回溯搜索
ks.printResult();
}
}
