背包演算法
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];
}