演算法背包問題
㈠ 用貪心演算法解決背包問題
用貪心演算法解決背包問題，首先要明白，結果不一定是全局最優的。對於貪心法而言，首先步驟是找到最優度量標准，我這里的演算法採用的最優度量標準是： 收益p/重量w 的值最大者優先放入背包中，所以有演算法如下：void GreedyKnapsack(float * x){ //前置條件：w[i]已按p[i]/w[i]的非增次序排列 float u=m; //u為背包剩餘載重量，初始時為m for(int i=0;i<n;i++) x[i]=0; //對解向量x初始化 for(i=0;i<n;i++){ //按最優度量標准選擇的分量 if(w[i]>u) break; x[i]=1.0; u=u-w[i]; } if(i<n) x[i]=u/w[i];}
㈡ 求背包問題貪心演算法實例結果
找零錢問題：以人民幣1元，2元，5元，10元，20元，50元，100元為例，要求所找的張數最少
背包問題：假設物體重量W1，W2．．．Wn其對應的價值為P1，P2．．．Pn，物體可分割，求裝入重量限制為m的背包中的物體價值最大．可用P/W來解答．
#include<iostream>
#include<algorithm>
using namespace std;
struct good//表示物品的結構體
{
double p;//價值
double w;//重量
double r;//價值與重量的比
}a[2000];
double s,value,m;
int i,n;
bool bigger(good a,good b)
{
return a.r>b.r;
}
int main()
{
scanf("%d",&n);//物品個數
for (i=0;i<n;i++)
{
scanf("%lf%lf",&a[i].w,&a[i].p);
a[i].r=a[i].p/a[i].w;
}
sort(a,a+n,bigger);//調用sort排序函數，你大概不介意吧，按照價值與重量比排序貪心
scanf("%lf",&m);//讀入包的容量m
s=0;//包內現存貨品的重量
value=0;//包內現存貨品總價值
for (i=0;i<n&&s+a[i].w<=m;i++)
{
value+=a[i].p;
s+=a[i].w;
}
printf("The total value in the bag is %.2lf.\n",value);//輸出結果
return 0;
}
㈢ 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數組還是會多選了，你看看。
㈣ 背包問題的演算法
1)登上演算法
用登山演算法求解背包問題 function []=DengShan(n,G,P,W) %n是背包的個數，G是背包的總容量，P是價值向量，W是物體的重量向量 %n=3;G=20;P=[25,24,15];W2=[18,15,10];%輸入量 W2=W; [Y,I]=sort(-P./W2);W1=[];X=[];X1=[]; for i=1:length(I) W1(i)=W2(I(i)); end W=W1; for i=1:n X(i)=0; RES=G;%背包的剩餘容量 j=1; while W(j)<=RES X(j)=1; RES=RES-W(j); j=j+1; end X(j)=RES/W(j); end for i=1:length(I) X1(I(i))=X(i); end X=X1; disp('裝包的方法是');disp(X);disp(X.*W2);disp('總的價值是：');disp(P*X');
時間復雜度是非指數的
2)遞歸法
先看完全背包問題
一個旅行者有一個最多能用m公斤的背包，現在有n種物品，每件的重量分別是W1，W2，...,Wn,
每件的價值分別為C1,C2,...,Cn.若的每種物品的件數足夠多.
求旅行者能獲得的最大總價值。
本問題的數學模型如下：
設 f(x)表示重量不超過x公斤的最大價值，
則 f(x）=max{f(x-i)+c[i]} 當x>=w[i] 1<=i<=n
可使用遞歸法解決問題程序如下:
program knapsack04;
const maxm=200;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
function f(x:integer):integer;
var i,t,m:integer;
begin
if x=0 then f:=0 else
begin
t:=-1;
for i:=1 to n do
begin
if x>=w[i] then m:=f(x-i)+c[i];
if m>t then t:=m;
end;
f:=t;
end;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
writeln(f(m));
end.
說明:當m不大時,編程很簡單,但當m較大時,容易超時.
4.2 改進的遞歸法
改進的的遞歸法的思想還是以空間換時間,這只要將遞歸函數計算過程中的各個子函數的值保存起來,開辟一個
一維數組即可
程序如下:
program knapsack04;
const maxm=2000;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
p:array[0..maxm] of integer;
function f(x:integer):integer;
var i,t,m:integer;
begin
if p[x]<>-1 then f:=p[x]
else
begin
if x=0 then p[x]:=0 else
begin
t:=-1;
for i:=1 to n do
begin
if x>=w[i] then m:=f(i-w[i])+c[i];
if m>t then t:=m;
end;
p[x]:=t;
end;
f:=p[x];
end;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
fillchar(p,sizeof(p),-1);
writeln(f(m));
end.
3)貪婪演算法
改進的背包問題：給定一個超遞增序列和一個背包的容量，然後在超遞增序列中選（只能選一次）或不選每一個數值，使得選中的數值的和正好等於背包的容量。
代碼思路：從最大的元素開始遍歷超遞增序列中的每個元素，若背包還有大於或等於當前元素值的空間，則放入，然後繼續判斷下一個元素；若背包剩餘空間小於當前元素值，則判斷下一個元素
簡單模擬如下：
#define K 10
#define N 10
＃i nclude <stdlib.h>
＃i nclude <conio.h>
void create(long array[],int n,int k)
{/*產生超遞增序列*/
int i,j;
array[0]=1;
for(i=1;i<n;i++)
{
long t=0;
for(j=0;j<i;j++)
t=t+array[j];
array[i]=t+random(k)+1;
}
}
void output(long array[],int n)
{/*輸出當前的超遞增序列*/
int i;
for(i=0;i<n;i++)
{
if(i%5==0)
printf("\n");
printf("%14ld",array[i]);
}
}
void beibao(long array[],int cankao[],long value,int count)
{/*背包問題求解*/
int i;
long r=value;
for(i=count-1;i>=0;i--)/*遍歷超遞增序列中的每個元素*/
{
if(r>=array[i])/*如果當前元素還可以放入背包，即背包剩餘空間還大於當前元素*/
{
r=r-array[i];
cankao[i]=1;
}
else/*背包剩餘空間小於當前元素值*/
cankao[i]=0;
}
}
void main()
{
long array[N];
int cankao[N]={0};
int i;
long value,value1=0;
clrscr();
create(array,N,K);
output(array,N);
printf("\nInput the value of beibao:\n");
scanf("%ld",&value);
beibao(array,cankao,value,N);
for(i=0;i<N;i++)/*所有已經選中的元素之和*/
if(cankao[i]==1)
value1+=array[i];
if(value==value1)
{
printf("\nWe have got a solution,that is:\n");
for(i=0;i<N;i++)
if(cankao[i]==1)
{
if(i%5==0)
printf("\n");
printf("%13ld",array[i]);
}
}
else
printf("\nSorry.We have not got a solution.\n");
}
貪婪演算法的另一種寫法，beibao函數是以前的代碼，用來比較兩種演算法：
#define K 10
#define N 10
＃i nclude <stdlib.h>
＃i nclude <conio.h>
void create(long array[],int n,int k)
{
int i,j;
array[0]=1;
for(i=1;i<n;i++)
{
long t=0;
for(j=0;j<i;j++)
t=t+array[j];
array[i]=t+random(k)+1;
}
}
void output(long array[],int n)
{
int i;
for(i=0;i<n;i++)
{
if(i%5==0)
printf("\n");
printf("%14ld",array[i]);
}
}
void beibao(long array[],int cankao[],long value,int count)
{
int i;
long r=value;
for(i=count-1;i>=0;i--)
{
if(r>=array[i])
{
r=r-array[i];
cankao[i]=1;
}
else
cankao[i]=0;
}
}
int beibao1(long array[],int cankao[],long value,int n)
{/*貪婪演算法*/
int i;
long value1=0;
for(i=n-1;i>=0;i--)/*先放大的物體，再考慮小的物體*/
if((value1+array[i])<=value)/*如果當前物體可以放入*/
{
cankao[i]=1;/*1表示放入*/
value1+=array[i];/*背包剩餘容量減少*/
}
else
cankao[i]=0;
if(value1==value)
return 1;
return 0;
}
void main()
{
long array[N];
int cankao[N]={0};
int cankao1[N]={0};
int i;
long value,value1=0;
clrscr();
create(array,N,K);
output(array,N);
printf("\nInput the value of beibao:\n");
scanf("%ld",&value);
beibao(array,cankao,value,N);
for(i=0;i<N;i++)
if(cankao[i]==1)
value1+=array[i];
if(value==value1)
{
printf("\nWe have got a solution,that is:\n");
for(i=0;i<N;i++)
if(cankao[i]==1)
{
if(i%5==0)
printf("\n");
printf("%13ld",array[i]);
}
}
else
printf("\nSorry.We have not got a solution.\n");
printf("\nSecond method:\n");
if(beibao1(array,cankao1,value,N)==1)
{
for(i=0;i<N;i++)
if(cankao1[i]==1)
{
if(i%5==0)
printf("\n");
printf("%13ld",array[i]);
}
}
else
printf("\nSorry.We have not got a solution.\n");
}
4)動態規劃演算法
解決0/1背包問題的方法有多種，最常用的有貪婪法和動態規劃法。其中貪婪法無法得到問題的最優解，而動態規劃法都可以得到最優解，下面是用動態規劃法來解決0/1背包問題。
動態規劃演算法與分治法類似，其基本思想是將待求解問題分解成若干個子問題，然後從這些子問題的解得到原問題的解。與分治法不同的是，適合於用動態規劃法求解的問題，經分解得到的子問題往往不是互相獨立的，若用分治法解這類問題，則分解得到的子問題數目太多，以至於最後解決原問題需要耗費過多的時間。動態規劃法又和貪婪演算法有些一樣，在動態規劃中，可將一個問題的解決方案視為一系列決策的結果。不同的是，在貪婪演算法中，每採用一次貪婪准則便做出一個不可撤回的決策，而在動態規劃中，還要考察每個最優決策序列中是否包含一個最優子序列。
0/1背包問題
在0 / 1背包問題中，需對容量為c 的背包進行裝載。從n 個物品中選取裝入背包的物品，每件物品i 的重量為wi ，價值為pi 。對於可行的背包裝載，背包中物品的總重量不能超過背包的容量，最佳裝載是指所裝入的物品價值最高，即p1*x1+p2*x1+...+pi*xi(其1<=i<=n，x取0或1，取1表示選取物品i) 取得最大值。
在該問題中需要決定x1 .. xn的值。假設按i = 1，2，...，n 的次序來確定xi 的值。如果置x1 = 0，則問題轉變為相對於其餘物品(即物品2，3，.，n)，背包容量仍為c 的背包問題。若置x1 = 1，問題就變為關於最大背包容量為c-w1 的問題。現設r?{c，c-w1 } 為剩餘的背包容量。
在第一次決策之後，剩下的問題便是考慮背包容量為r 時的決策。不管x1 是0或是1，[x2 ，.，xn ] 必須是第一次決策之後的一個最優方案，如果不是，則會有一個更好的方案[y2，.，yn ]，因而[x1，y2，.，yn ]是一個更好的方案。
假設n=3, w=[100,14,10], p=[20,18,15], c= 116。若設x1 = 1，則在本次決策之後，可用的背包容量為r= 116-100=16 。[x2，x3 ]=[0,1] 符合容量限制的條件，所得值為1 5，但因為[x2，x3 ]= [1，0] 同樣符合容量條件且所得值為1 8，因此[x2，x3 ] = [ 0，1] 並非最優策略。即x= [ 1，0，1] 可改進為x= [ 1，1，0 ]。若設x1 = 0，則對於剩下的兩種物品而言，容量限制條件為116。總之，如果子問題的結果[x2，x3 ]不是剩餘情況下的一個最優解，則[x1，x2，x3 ]也不會是總體的最優解。在此問題中，最優決策序列由最優決策子序列組成。假設f (i,y) 表示剩餘容量為y，剩餘物品為i，i + 1，...，n 時的最優解的值，即：利用最優序列由最優子序列構成的結論，可得到f 的遞歸式為：
當j>=wi時： f(i,j)=max{f(i+1,j),f(i+1,j-wi)+vi} ①式
當0<=j<wi時：f(i,j)=f(i+1,j) ②式
fn( 1 ,c) 是初始時背包問題的最優解。
以本題為例：若0≤y＜1 0，則f ( 3 ,y) = 0；若y≥1 0，f ( 3 ,y) = 1 5。利用②式，可得f (2, y) = 0 ( 0≤y＜10 )；f(2，y)= 1 5(1 0≤y＜1 4)；f(2，y)= 1 8(1 4≤y＜2 4)和f(2，y)= 3 3(y≥2 4)。因此最優解f ( 1 , 11 6 ) = m a x {f(2，11 6)，f(2，11 6 - w1)+ p1} = m a x {f(2，11 6)，f(2，1 6)+ 2 0 } = m a x { 3 3，3 8 } = 3 8。
現在計算xi 值，步驟如下：若f ( 1 ,c) =f ( 2 ,c)，則x1 = 0，否則x1 = 1。接下來需從剩餘容量c-w1中尋求最優解，用f (2, c-w1) 表示最優解。依此類推，可得到所有的xi (i= 1.n) 值。
在該例中，可得出f ( 2 , 116 ) = 3 3≠f ( 1 , 11 6 )，所以x1 = 1。接著利用返回值3 8 -p1=18 計算x2 及x3，此時r = 11 6 -w1 = 1 6，又由f ( 2 , 1 6 ) = 1 8，得f ( 3 , 1 6 ) = 1 4≠f ( 2 , 1 6 )，因此x2 = 1，此時r= 1 6 -w2 = 2，所以f (3,2) =0，即得x3 = 0。
㈤ C語言演算法求助：背包問題
//如果每種商品只有一件，是0-1背包問題
讀入的數據N代表物品個數
V代表背包容量。
//對於你的例子
，輸入為
//5
16
//2
3
//3
2
//4
3
//5
7
//6
9
//輸出為21
#include
<iostream>
using
namespace
std;
#define
MAXSIZE
1000
int
f[MAXSIZE
+
1],
c[MAXSIZE
+
1],
w[MAXSIZE
+
1];
int
main()
{
int
N,
V;
cin
>>
N
>>
V;
int
i
=
1;
for
(;
i
<=
N;
++i)
{
cin
>>
c[i]
>>
w[i];
}
for
(i
=
1;
i
<=
N;
++i)
{
for
(int
v
=
V;
v
>=
c[i];
--v)
//c[i]可優化為bound,
bound
=
max
{V
-
sum
c[i,...n],
c[i]}
{
f[v]
=
(f[v]
>
f[v
-
c[i]]
+
w[i]
?
f[v]
:
f[v
-
c[i]]
+
w[i]);
}
}
//當i=N時，可以跳出循環單獨計算F[V]
cout
<<
f[V]
<<
'\n';
system("pause");
return
0;
}
//如果每種可以有多個，是完全背包問題，
㈥ C語言 貪心演算法求背包問題
是你的冒泡排序出了問題~
你吧 原來的1-2-3號按照東西的價值重新排列現在的1-2-3對應原來的2-1-3了
所以 你輸出的時候是按 1-2-3輸出的話 就等於第一個是原來的X2 第二個是X1第三個是X3
而且你的冒泡排序用錯了 只比較了 P[0]/K[0]和P[1]/K[1] P[1]/K[1]和P[2]/K[2]
周一我去學校幫你重新改改 我家的機器沒有C++
周一晚上我會上傳答案~我最近正好也要做演算法的作業~
#include <stdio.h>
#include <math.h>
#define N 50
float find(float p[N],float w[N],float x[N] ,float M,int n) /*先放單位價值量大的物體，再考慮小的物體*/
{
int i;
float maxprice;
for (i = 0; i < n; i++)
x[i] = 0;
i = 0;
maxprice=0;
while (i < n && w[i] < M)
{
M=M-w[i];
x[i] =w[i]; /* 表示放入數量 */
maxprice=maxprice+p[i];
x[n-1]=M;
i++;
}
if (i < n &&M> 0)
{
maxprice=maxprice+p[i]*x[i]/w[i];
i++;
}
return maxprice;
}
int main()
{
int n,flag=1;
float temp,M,w[N],p[N],x[N];
int a[N],b[N];
int k,j,l=0;
printf(
㈦ C語言背包問題遞歸演算法
你學過數據結構了嗎？如果學過，那就比較好理解，該演算法的思路和求二叉樹的高度的演算法的思路是十分類似的。把取這i個物體看成i個階段，則該二叉樹有i+1層。其中空背包時為根結點，左孩子則為放棄了第1個物品後的背包，右孩子為選取了第1個物品後的背包。今後在對第i個物品進行選擇時，向左表示放棄，向右表示選取。則遞歸演算法可如下：
int fun(int s, int i, int n) //s傳入的是背包容量, i是進行第i個物品的選取，n為剩餘物品的件數
{
if(s == 0) return 有解；
else if(剩餘的每件物品都裝不進|| n == 0) return 無解；
L = fun(s, i + 1, n - 1); //放棄第i個物品，則下一步的背包容量仍為s，然後看其是否有解，(遞歸調用進入左子樹)
R = fun(s - wi, i + 1, n - 1); //選取第i個物品，則下一步的背包容量為s-wi，然後看其是否有解，(遞歸調用進入右子樹)
return (l, r); //綜合考慮左右兩邊，看哪邊是正解或都無解。其實應該返回 return (L||R);
}
㈧ 貪心演算法 部分背包問題
這道題是dp的思想啦，動態規劃
(1)背包問題最優值的結構
動態規劃的逆向思維法的第一步是刻畫一個最優值的結構，如果我們能分析出一個問題的最優值包含其子問題的最優值，問題的這種性質稱為最優子結構。一個問題的最優子結構性質是該問題可以使用動態規劃的顯著特徵。
對一個負重能力為m的背包，如果我們選擇裝入一個第 i 種物品，那麼原背包問題就轉化為負重能力為 m-w[i] 的子背包問題。原背包問題的最優值包含這個子背包問題的最優值。若我們用背包的負重能力來劃分狀態，令狀態變數s[k]表示負重能力為k的背包，那麼s[m]的值只取決於s[k](k≤m)的值。因此背包問題具有最優子結構。
(2)遞歸地定義最優值
動態規劃的逆向思維法的第二步是根據各個子問題的最優值來遞歸地定義原問題的最優值。對背包問題而言，有狀態轉移方程：
／max{s[k-w[i]]+v[i]}(其中1≤i≤n，且k-w[i]≥0)
s[k]= 若k>0且存在1≤i≤n使k-w[i]≥0，
＼ 0 否則。
有了計算各個子問題的最優值的遞歸式，我們就可以直接編寫對應的程序。下述的函數knapsack是輸入背包的負重能力k，返回對應的子背包問題的最優值s[k]：
㈨ 用動態規劃演算法怎樣求解01背包問題
動態規劃主要解決的是多階段的決策問題。
01背包中，狀態為背包剩餘的容量，階段是每一個物品，決策是是否選擇當前的物品。
所以用動態規劃來解決是非常貼切的。
我們設f[V]表示已經使用容量為V時所能獲得的最大價值，w[i]表示i物品的質量，c[i]表示i物品的價值。
for(inti=1;i<=n;i++)
for(intj=V;j>=w[i];j--)
f[j]=max(f[j],f[j-w[i]]+c[i]);
這便是所謂的一個狀態轉移方程。
f[j]表示在已經使用容量為j時的最大價值，f[j-w[i]]表示在已經使用容量為j-w[i]時的最大價值。
f[j]可以由f[j-w[i]]這個狀態轉移到達，表示選取w[i]這個物品，並從而獲得價值為c[i]。
而每次f[j]會在選與不選中決策選出最優的方案。
從每一個物品，也就是每一個階段的局部最優推出最後的全局最優值。這樣就解決了01背包問題
㈩ 背包問題用分治演算法怎麼解決
分治演算法的基本思想是將一個規模為N的問題分解為K個規模較小的子問題，這些子問題相互獨立且與原問題性質相同。求出子問題的解，就可得到原問題的解。
我的想法是，比如背包承重是m，物品t[]分別是t1,t2,...tn,
演算法pakage(m,t[],p[])，最簡單的演算法思路就是把物品ti(1<=i<=n)放入背包，然後問題就變成在背包m-ti的承重下，盛放物品newt[](newt[]=t[]-ti)，用遞歸方法可以很簡單的描述，最後p[]就是得到的結果.但是這么做演算法復雜度非常高，所以必須優化。只是給你提供一個思路，希望有用
pakage(m,t[],p[]){
if(m==0||t.length()==0){
return;
}
if(null!=t){
for(int i=0;i<t.length;i++){
//把t[i]放入背包
//newt[]=t-t[i];
package(m-t[i],newt[],p[]);
}
}
}