背包算法
1. 0/1背包 回溯算法
#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);
}
}
2. 急，分全拿出来了，算法中的背包问题的贪心算法
#include <stdio.h>
#include <iostream.h>
#define MAXWEIGHT 20
#define n 3
float pw[n]={0},x[n]={0};
int w[n]={0},p[n]={0};
void sort(int p[],int w[])
{
int temp1,temp2;
float temp;
int i,j;
for(i=0;i<n;i++)
{
pw[i]=float(p[i])/w[i];
}
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(pw[i]<pw[j])
{
temp=pw[i],pw[i]=pw[j],pw[j]=temp;
temp1=p[i],temp2=w[i];
p[i]=p[j],w[i]=w[j];
p[j]=temp1,w[j]=temp2;
}
}
}
}
void GreedyKnapsack(int p[],int w[])
{
int m=MAXWEIGHT,i;
for(i=0;i<n;i++) x[i]=0.0;
for(i=0;i<n;i++)
{
if(w[i]>m) break;
x[i]=1.0;
m=m-w[i];
}
if(i<n) x[i]=float(m)/w[i];
}
void main()
{
int i;
printf("请输入每个物体的效益和重量:\n");
for(i=0;i<n;i++)
{
cin>>p[i]>>w[i];
}
for(i=0;i<n;i++)
{
printf("原物体%d的效益和重量分别为%d,%d:\n",i+1,p[i],w[i]);
}
sort(p,w);
printf("\n\n\n按效益值非递增顺序排列物体:\n");
for(i=0;i<n;i++)
{
printf("物体%d的效益和重量分别为%d,%d 效益值为:%f\n",(i+1),p[i],w[i],pw[i]);
}
GreedyKnapsack(p,w);
printf("\n\n\n最优解为:\n");
for(i=0;i<n;i++)
{
printf("第%d个物体要放%f:\n",i+1,x[i]);
}
}
这是正确的算法
3. 多个背包的问题，求算法
先不管m；全装进盒子里；需x个；再将每个盒子的武器数从小到大排好；就j：=1；用repeat至x-j+1=m;输出j至m的武器总数。高加错在哪知道了,xiexie!
4. 0-1背包问题用什么实现算法最好
我们书上给的0-1背包问题是是用动态规划方法做的这个算法是动态规划的典型应用所以你把动态规划的思想搞清楚就应该可以理解了下面我把动态规划的思想给你说一下,希望对你有所帮助.哦..不好意思..时间不多了..你自己到网上找一下这方面的思想..然后结合一个实例认真研读一下..弄懂之后..你对动态规划..0-1背包问题就会有比较深入的理解.建议好好学一下算法..这对计算机专业学生来说很重要..我越来越觉得祝学有所成
5. c语言 背包问题 递归算法
if(n==0)应该改成
if(n<0)才对，表示没有物品可选了。我的一个改进，但输出选择项还是有问题！
#include<stdio.h>
#include<conio.h>
#defineN3
intMaxW(intn,intC,int*Volume,int*Weight,int*Select){
intW=0,W1=0;
if(n<0){//没有物品了
return0;
}
W=MaxW(n-1,C,Volume,Weight,Select);//没放入n之前的重量
if(C>=Volume[n]){//背包剩余空间可以放下物品n
W1=MaxW(n-1,C-Volume[n],Volume,Weight,Select)+Weight[n];//放入n所能得到的重量
Select[n]=0;
if(W1>W){//放入n能获得更大的重量
Select[n]=1;
W=W1;
}
}
returnW;
}
intmain(){
intC=8,W,i;
//intVolume[N]={1,2,3,4,5};//物品体积
//intWeight[N]={1,2,5,7,8};//物品重量
intVolume[N]={2,3,5};//物品体积
intWeight[N]={5,8,7};//物品重量
intSelect[N]={0};//选择标记
W=MaxW(N-1,C,Volume,Weight,Select);
printf("MaxWeight=%d,SelectList[index(volume,weight)]: ",W);
for(i=0;i<N;++i){
if(Select[i]){
printf("%d(%d,%d)",i,Volume[i],Weight[i]);
}
}
printf(" Finished! ");
getch();
return0;
}
其中的Select数组还是会多选了，你看看。
6. 背包问题的算法
3.2 背包问题
背包问题有三种
1.部分背包问题
一个旅行者有一个最多能用m公斤的背包，现在有n种物品，它们的总重量分别是W1，W2，...,Wn,它们的总价值分别为C1,C2,...,Cn.求旅行者能获得最大总价值。
解决问题的方法是贪心算法:将C1/W1,C2/W2,...Cn/Wn,从大到小排序,不停地选择价值与重量比最大的放人背包直到放满为止.
2.0/1背包
一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn.若每种物品只有一件求旅行者能获得最大总价值。
<1>分析说明:
显然这个题可用深度优先方法对每件物品进行枚举(选或不选用0,1控制).
程序简单,但是当n的值很大的时候不能满足时间要求，时间复杂度为O（2n）。按递归的思想我们可以把问题分解为子问题,使用递归函数
设 f(i，x)表示前i件物品，总重量不超过x的最优价值
则 f（i，x）=max(f(i－1，x-W[i])+C[i]，f（i－1，x））
f（n，m）即为最优解，边界条件为f（0，x）＝0 ，f(i,0)=0;
动态规划方法(顺推法)程序如下:
程序如下：
program knapsack02;
const maxm=200;maxn=30;
type ar=array[1..maxn] of integer;
var m,n,j,i:integer;
c,w:ar;
f:array[0..maxn,0..maxm] of integer;
function max(x,y:integer):integer;
begin
if x>y then max:=x else max:=y;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
for i:=1 to m do f(0,i):=0;
for i:=1 to n do f(i,0):=0;
for i:=1 to n do
for j:=1 to m do
begin
if j>=w[i] then f[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j])
else f[i,j]:=f[i-1,j];
end;
writeln(f[n,m]);
end.
使用二维数组存储各子问题时方便，但当maxm较大时如maxn=2000时不能定义二维数组f,怎么办,其实可以用一维数组,但是上述中j:=1 to m 要改为j:=m downto 1,为什么?请大家自己解决。
3.完全背包问题
一个旅行者有一个最多能用m公斤的背包，现在有n种物品，每件的重量分别是W1，W2，...,Wn,
每件的价值分别为C1,C2,...,Cn.若的每种物品的件数足够多.
求旅行者能获得的最大总价值。
本问题的数学模型如下：
设 f(x)表示重量不超过x公斤的最大价值，
则 f(x）=max{f(x-w[i])+c[i]} 当x>=w[i] 1<=i<=n
程序如下:（顺推法）
program knapsack04;
const maxm=2000;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
f:array[0..maxm] of integer;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
f(0):=0;
for i:=1 to m do
for j:=1 to n do
begin
if i>=w[j] then t:=f[i-w[j]]+c[j];
if t>f[i] then f[i]:=t
end;
writeln(f[m]);
end.
7. 背包算法的使用
program p;
var
v,w,m:array[1..100] of integer;
i,j,n,t,s,z:integer;
begin
write('input n:');
readln(n);
for i:=1 to n do
begin
write('input v:');
readln(v[i]);
write('input w:');
readln(w[i]);
m[i]:=i;
end;
write('input s:');
readln(s);
for i:=1 to n-1 do
for j:=i+1 to n do
if v[i] div w[i]<v[j] div w[j] then
begin
t:=m[i];
m[i]:=m[j];
m[j]:=t;
t:=v[i];
v[i]:=v[j];
v[j]:=t;
t:=w[i];
w[i]:=w[j];
w[j]:=t;
end;
for i:=1 to n do
begin
if s>w[i] then
begin
writeln(i,':No.',m[i],'*',w[i],',all:',v[i]);
z:=z+v[i];
end;
if s<w[i] then
begin
writeln(i,':No.',m[i],'*',s,',all:',v[i] div w[i]*s);
z:=z+v[i] div w[i]*s;
end;
s:=s-w[i];
if w[i]<=0 then
break;
end;
writeln('all the are:',z);
readln;
end.
背包的题目我就不多说了，在网上就能找到的，看完题，在看代码
这是pascal代码。
8. 求背包问题（贪婪算法（c语言））
c/w 排序，选择，以v为闸值，若w过大，选下一个，选完，得结果。
很简单的
9. 背包问题的贪心算法C＋＋
为啥不用动态规划呢？
背包的贪心法是每次都选择收益最大，如果包还能容纳，就放入包里面，并把这个物品去掉。
10. 背包算法的C#代码
背包问题
有一个箱子容量为v，同时有n个物品，每个物品有一个体积（正整数）。设计一个算法在n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
动态规划
c#版算法
//体积表：当不同的参照物时，在各种体积箱子下，最大的占用体积
static
int[,]
vols
=
new
int[100,
100];
///
<summary>
///
取若干个装入箱内，使箱子的剩余空间为最小。
///
</summary>
///
<param
name="cap">箱子的容量</param>
///
<param
name="objects">所有的物品</param>
///
<returns>剩下的容量</returns>
static
int
package(int
cap,
int[]
objects)
{
int
count
=
objects.length;
if
(count
==
0)
return
cap;
int
i,
j;
for
(i
=
0;
i
<
100;
i++)
for
(j
=
0;
j
<
100;
j++)
vols[i,
j]
=
0;
//初始化体积表
for
(i
=
1;
i
<
count
+
1;
i++)
{
for
(j
=
1;
j
<
cap
+
1;
j++)
{
//如果当前物品的体积小于背包容量
if
(objects[i]
<=
j)
{
//如果本物品的体积加上箱子剩下的容量能放的物品的体积大于上一次选择的最佳方案则更新vols[i][j]
if
(objects[i]
+
vols[i
-
1,
j
-
objects[i]]
>
vols[i
-
1,
j])
{
vols[i,
j]
=
objects[i]
+
vols[i
-
1,
j
-
objects[i]];
}
else
{
vols[i,
j]
=
vols[i
-
1,
j];
}
}
else
{
vols[i,
j]
=
vols[i
-
1,
j];
}
}
}
return
cap
-
vols[count,
cap];
}