Question

简单c++问题（加100分）

0、1背包的思路及程序（请说得详细一些）
谢谢！！
c++

Answer 1

用动态规划来解背包问题
在历届NOIP竞赛中，有4道初赛题和5道复赛题均涉及到背包问题，所谓的背包问题，可以描述如下：一个小偷打劫一个保险箱，发现柜子里有N类不同大小与价值的物品，但小偷只有一个容积为M的背包来装东西，背包问题就是要找出一个小偷选择所偷物品的组合，以使偷走的物品总价值最大。
如有4件物品，容积分别为： 3 4 5 8
对应的价值分别为： 4 5 7 10
小偷背包的载重量为：12
则取编号为1 2 3的物品，得到最大价值为16。
算法分析：如果采用贪心法，则先取价值最大的10，消耗了容积8，下面只能取容积为4的物品，得到价值5，这样总价值是15，这不是最优解，因此贪心法是不正确的。
采用穷举法，用一个B数组来表示取数的标记，当B[i]=0时表示第i件物品不取，当B[i]=1时表示第i件物品已取，初始化全部取0，以下算法是从后面的物品开始取起，通过B数组的取值把15种取法全部穷举出来，价值MAX初始化为0。
B[0] B[1] B[2] B[3] B[4]
0 0 0 0 0 {初始化}
0 0 0 0 1 {取第4件物品，容积为8，不超，价值为10，将MAX替换为10}
0 0 0 1 0 ｛取物品3，容积为5，不超，价值为7，不换｝
0 0 0 1 1 ｛取物品3、4，容积为13，超｝
0 0 1 0 0 ｛取物品2，容积为4，不超，价值为5，不换｝
0 0 1 0 1
0 0 1 1 0
0 0 1 1 1
……
0 1 1 1 0 ｛这是最佳方案｝
0 1 1 1 1
1 0 0 0 0 ｛当B〔0〕＝1时停止，B〔0〕称为哨兵｝
生成B数组中数据的方法如下：
fillchar(b,sizeof(b),0);
while b[0]=0 do
begin j:=n;
while b[j]=1 do dec(j);
b[j]:=1;
for i:=j+1 to n do
b[i]:=0;
end；
小结：以上每件物品只能取1件，所以取法只有0和1两种情况，我们称之为0、1背包，算法的时间复杂度为O（2N），在1秒内N只能做到20。
例1：选数（NOIP2002 初中组复赛第2题）
[问题描述]:已知 n 个整数 x1,x2,…,xn，以及一个整数 k（k＜n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k＝3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为：
3＋7＋12=22 3＋7＋19＝29 7＋12＋19＝38 3＋12＋19＝34。
现在，要求你计算出和为素数共有多少种。
例如上例，只有一种的和为素数：3＋7＋19＝29。
[输入]：
键盘输入，格式为：
n , k （1<=n<=20，k＜n）
x1,x2，…,xn （1<=xi<=5000000）
n[输出]：
屏幕输出，格式为：
一个整数（满足条件的种数）。
[输入输出样例]:
输入：
4 3
3 7 12 19
输出：
1
[算法分析]:本题应用背包问题中取数的方法进行穷举，在取数的过程中，当B数组中有K个1的时候将对应的K个数相加，再判断是不是素数。
主要程序段如下：
readln(n,k); sum:=0;
for i:=1 to n do read(a[i]);
fillchar(b,sizeof(b),0);
while b[0]=0 do
begin j:=n;
while b[j]=1 do dec(j);
b[j]:=1;
for i:=j+1 to n do b[i]:=0;
m:=0;
for i:=1 to n do
if b[i]=1 then m:=m+1; {统计1的个数}
if m=k then
begin 计算此种取数方法得到的和S；
if S 是素数 then sum:=sum+1;
end;
end;
例2：采药(NOIP2005 初中组复赛第3题)
【问题描述】
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？

【输入文件】
输入文件medic.in的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
【输出文件】
输出文件medic.out包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
【样例输入】
70 3
71 100
69 1
1 2
【样例输出】
3
【数据规模】
对于30%的数据，M <= 10；
对于全部的数据，M <= 100。
【算法分析】本题如果采用上述方法来解，只能将M算到20，而这里M〈=100，所以只能拿30%的分数，比较好的算法是采用动态规划，为了能说清算法，现重新举一个例子，若输入：
10 3
3 4
4 5
5 6
表示背包的容量是10，有3种物品。用一个数组用来表示背包容量与其最大价值的关系，上例中设置一个数组count,用下标表示容量，初始化为0。然后按物品的顺序一一来统计此时的最大价值，每种药品对应各种背包容量时得到的最大价值为：
对于是第i件物品，背包容量为j时的最大价值Cmax(j)=MAX(Cmaxj,Pi+余下空间的最大价值Cmax(j-i物品所占的空间))，如上例中，根据物品的不断增加，各容量背包得到的最大价值不断替换：

容量 1 2 3 4 5 6 7 8 9 10
价值
序号 0 0 0 0 0 0 0 0 0 0
1 0 0 4 4 4 4 4 4 4 4
2 0 0 4 5 5 5 9 9 9 9
3 0 0 4 5 6 6 9 10 11 11

[数据结构] time,price数组分别用来存入时间和价值，count来存入背包的价值。
var
time,price:array[1..100] of longint;
t:longint; i,m,j:integer;
count:array[0..1000] of longint;
begin
assign(input,'medic.in');
assign(output,'medic.out');
reset(input);
rewrite(output);
readln(t,m);
for i:=1 to m do
readln(time[i],price[i]);
fillchar(count,sizeof(count),0);
for i:=1 to m do
for j:=t downto 1 do
begin
if (j>=time[i]) and (price[i]+count[j-time[i]]>count[j]) then
count[j]:=price[i]+count[j-time[i]];
end; {j>=time[i]表示当前的容量能放入背包，price[i]+count[j-time[i]]>count[j]表示第i件物品的价值加上第i件物品对于背包容量为j时余下空间的最大价值大于当前背包容量为j时的最大价值}
writeln(count[t]);
close(input);
close(output);
end.
例3：开心的金明（NOIP2006 初中组复赛第2题）
题目较长，省略，本题与例2相比，在比较时要先将价值乘以一个数，其余一样，但要注意的是：本题N的范围是<=26，如果用0、1背包穷举法在1秒内只能过10个点中的8个点。
总结：采用动态规划的时间复杂度为O(n*m)，范围比穷举法大多了，但也有弱点，当数据不是整数时，就不可使用；如果还要求出具体的取法，那也相当麻烦。

Answer 2

题目
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
基本思路
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。那么，如果只用一个数组f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下：
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符，但它却是另一个重要的背包问题P02最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。
事实上，使用一维数组解01背包的程序在后面会被多次用到，所以这里抽象出一个处理一件01背包中的物品过程，以后的代码中直接调用不加说明。
过程ZeroOnePack，表示处理一件01背包中的物品，两个参数cost、weight分别表明这件物品的费用和价值。
procedure ZeroOnePack(cost,weight)
for v=V..cost
f[v]=max{f[v],f[v-cost]+weight}

有了这个过程以后，01背包问题的伪代码就可以这样写：
for i=1..N
ZeroOnePack(c[i],w[i]);
初始化的细节问题

如果是第一种问法，要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。
如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。
前面的伪代码中有 for v=V..1，可以将这个循环的下限进行改进。
由于只需要最后f[v]的值，倒推前一个物品，其实只要知道f[v-w[n]]即可。以此类推，对以第j个背包，其实只需要知道到f[v-sum{w[j..n]}]即可，即代码中的
for i=1..N
for v=V..0
可以改成
for i=1..n
bound=max{V-sum{w[i..n]},c[i]}
for v=V..bound
这对于V比较大时是有用的。

#include<fstream>
using namespace std;
struct bag{
double w;
double p;
double p_w;
int order;
}; //说明物品特性

void sort(struct bag *a,int low,int high);

int main()
{
int n,i;
double *x;
double m,cost=0;
struct bag *b; //结构数组，用于表示所有物品
//定义文件流并与具体的磁盘文件相关联
ifstream fin;
fin.open("背包问题_in.txt");

ofstream fout;
fout.open("背包问题_out.txt");

//输入物品数目 n 背包容量 M
fin>>n>>m;

//动态分配存储空间
b=new struct bag[n];
x=new double[n];

for(i=0;i<n;i++){
fin>>b[i].w>>b[i].p; //输入物品重量和运价
b[i].p_w=b[i].p/b[i].w; //求出运价重量比
b[i].order=i; //贴标签
}

sort(b,0,n-1); //按运价重量比从大到小进行排序

for(i=0;i<n;i++)
x[i]=0; //初始化解向量

for(i=0;i<n;i++) //处理所有物品
if(b[i].w<=m){ //若背包能放得下整个物品
x[b[i].order]=1; //放入背包
m-=b[i].w; //背包剩余容量减小
cost+=b[i].p; //总价值增加
}
else{ //否则，放不下整个物品
x[b[i].order]=m/b[i].w; //放一部分
cost+=x[b[i].order]*b[i].p; //总价值增加
break; //打断，后续物品由于不能放入背包，不需处理
}

for(i=0;i<n;i++)
fout<<x[i]<<"\t"; //输出解向量
fout<<endl<<cost;

//删除动态分配下的空间
delete []x;
delete []b;

//关闭文件指针
fin.close();
fout.close();

return 0;
}

int par(struct bag *a,int low,int high)
{
struct bag temp;
temp=a[low];
double t;
t=a[low].p_w;
while(low<high){
while(low<high && a[high].p_w<=t)
--high;
a[low]=a[high];
while(low<high && a[low].p_w>=t)
++low;
a[high]=a[low];
}
a[low]=temp;
return low;
}

void sort(struct bag *a,int low,int high)
{
int loc;
if(low<high){
loc=par(a,low,high);
sort(a,low,loc-1);
sort(a,loc+1,high);
}
}

Answer 3

上面的都太麻烦太多太难看了~~~
#define SIZE 4

void try(int i,int n,int weight[],int value[],int weightLimit,int solution[],int bestSolution[]);
void saveSolution(int solution[],int bestSolution[],int size);
int getWeight(int solution[],int weight[],int size);
int getValue(int solution[],int value[],int size);
void printSolution(int solution[],int size);

main()
{
int i,weightLimit=50;
int solution[SIZE+1]={0};
int bestSolution[SIZE+1]={0};
int weight[SIZE+1]={0,16,15,15,20};
int value[SIZE+1]={0,45,25,25,30};

try(1,SIZE,weight,value,weightLimit,solution,bestSolution);

for(i=1;i<=SIZE;i++)
printf("%d\t",bestSolution[i]);

system("pause");
return 0;
}

void try(int i,int n,int weight[],int value[],int weightLimit,int solution[],int bestSolution[])
{
int xi;

for(xi=0;xi<=1;xi++){
solution[i]=xi;

if (getWeight(solution,weight,n)<=weightLimit){
if(i==n){//求一元组，不再递归
//printSolution(bestSolution,n);
if(getValue(solution,value,n)>getValue(bestSolution,value,n))
saveSolution(solution,bestSolution,n);//将当前方案作为最大值方案
}
else
try(i+1,n,weight,value,weightLimit,solution,bestSolution);
}
solution[i]=0;
}
}

void saveSolution(int solution[],int bestSolution[],int size)
{
int i;
for(i=1;i<=size;i++)
bestSolution[i]=solution[i];
}

int getWeight(int solution[],int weight[],int size)
{
int totalWeight=0,i;
for(i=1;i<=size;i++)
totalWeight+=solution[i]*weight[i];

return totalWeight;
}

int getValue(int solution[],int value[],int size)
{
int totalValue=0,i;
for(i=1;i<=SIZE;i++)
totalValue+=solution[i]*value[i];

return totalValue;
}

void printSolution(int solution[],int size)
{
int i;
for(i=1;i<=size;i++)
printf("%2d",solution[i]);

printf("\n");
}

Answer 4

还是自己看书，比较实在点。