A. 完全背包問題（c語言，pascal）
4.1 原始遞歸法
先看完全背包問題
一個旅行者有一個最多能用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.
B. 哪位大神能幫我寫一個「完全背包」問題的代碼么謝謝！！ 最好用c或者c++ 寫，有測試數據更～～～
完全背包問題，f[v] = max{f[v], f[v - w[i]] + v[i]}; 狀態方程，用動態規劃做網路下會有的
http://ke..com/view/841810.htm
C. 求完全背包問題的代碼(C語言或C++版)或演算法
背包問題小結- []2006-07-28
做到背包問題覺得很有意思，寫寫看看。
完全背包問題可以用貪心演算法。
代碼如下：
program bag1;
const maxn=10;
var
goods:array[1..maxn,1..3] of integer;
s:array[1..maxn] of real;
i,j:integer;
m,n:integer;
y:integer;
x:real;
function max:integer;
var m:real;
i,j:integer;
begin
m:=0;
for i:=1 to n do
if (goods[i,3]=0) and (m max:=j;
end;
procere choose;
var i,j:integer;
begin
while y begin
if y begin
i:=max;
if m>=y+goods[i,1] then begin goods[i,3]:=1;x:=x+goods[i,2];y:=y+goods[i,1];end else
begin
x:=x+(m-y)*s[i];
y:=m;
end;
end;
end;
end;
begin
fillchar(goods,sizeof(goods),0);
assign(input,'b.txt');
reset(input);
readln(m,n);
for j:=1 to n do
read(goods[j,1]);
readln;
for j:=1 to n do
read(goods[j,2]);
for j:=1 to n do
s[j]:=goods[j,2]/goods[j,1];
close(input);
choose;
writeln(x:5:2);
end.
編得不是很好 ^-^ 獻丑了。
我來說說0/1背包問題。
狀態：當前物品n
算符：j=0（當前物品不放入背包） 或 j=1（當前物品放入背包）
這就很好說了，還是把yes函數一改，問題OK了。
代碼如下：
program bag2;
const maxn=10;
var i:integer;
goods:array[1..maxn,1..3] of integer;{原始數據}
s:array[1..maxn] of integer;{當前的狀態}
r:array[1..maxn] of integer;{當前的總質量}
m:integer;{背包容量}
max:integer;{物品個數}
procere try(n:integer);
var j:integer;
{function yes:boolean;
var k:integer;
t:integer;
mn:integer;
begin
mn:=0;
t:=goods[n,3];
goods[n,3]:=j;
for k:=1 to n do
if goods[k,3]=1 then inc(mn,goods[k,1]);
goods[n,3]:=t;
if mn>m then yes:=false else yes:=true;
end;}
begin
if n=max+1 then begin if x for i:=1 to max do s[i]:=goods[i,3]; {保存最優解}end
end else
begin
if r[n-1]>m then exit;{已超過背包總容量}
for j:=1 downto 0 do
begin
if j=1 then r[n]:=r[n-1]+goods[n,1];
if j=0 then r[n]:=r[n]-goods[n,1];
if {yes}r[n]<=m then begin goods[n,3]:=j;try(n+1);goods[n,3]:=0;end
end;
end;
end;
begin
assign(input,'b.txt');
reset(input);
readln(m,max);
for i:=1 to max do
read(goods[i,1]);
readln;
for i:=1 to max do
read(goods[i,2]);
close(input);
try(1);
for i:=1 to 7 do
write(s[i]:3);
writeln;
writeln(x);
end.
用yes 函數要從頭到當前求已裝入背包物品的總質量，時間效率不高。所以我們引入r[n]數組來記錄當前背包總質量（很好用！）注意用r[n-1]>m來做剪枝，以再次提高時間效率。
DC跟我說可以用二進制解此類問題。我覺得很有創意，也說說。比如8個物品，每個物品有0/1兩種狀態所以我們從(00000000)(二進制 )到（11111111）（二進制）循環即可。然後在分離十進制數對應起來即可。但在實際的操作中發現效率比回溯還低，我想有兩方面的原因：1、顯而易見，不可能做剪枝。2、每一次結果都要從1到8求和十效率降低。不過這確實是一種很新穎的演算法。
D. 背包問題C語言簡短代碼，大神們最好帶解釋和注釋，謝謝！！！
不知道你說的哪種類型的背包，我就說下最簡單的吧。
一、01背包
問題描述：有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。
（1）基本思路：這是最基礎的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。
用子問題定義狀態：即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀態轉移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。
意思簡要來說就是：如果不放第i件物品，那麼問題就轉化為「前i-1件物品放入容量為v的背包中」，價值為f[i-1][v]；如果放第i件物品，那麼問題就轉化為「前i-1件物品放入剩下的容量為v-c[i]的背包中」，此時能獲得的最大價值就是f[i-1][v-c[i]]再加上通過放入第i件物品獲得的價值w[i]。
（2）優化空間復雜度：以上方法的時間和空間復雜度均為O(N*V)，其中時間復雜度基本已經不能再優化了，但空間復雜度卻可以優化到O(V)。
先考慮上面講的基本思路如何實現，肯定是有一個主循環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]]推知，與本題意不符。
（3）初始化的細節問題：我們看到的求最優解的背包問題題目中，事實上有兩種不太相同的問法。有的題目要求「恰好裝滿背包」時的最優解，有的題目則並沒有要求必須把背包裝滿。一種區別這兩種問法的實現方法是在初始化的時候有所不同。
如果是第一種問法，要求恰好裝滿背包，那麼在初始化時除了f[0]為0其它f[1..V]均設為-∞，這樣就可以保證最終得到的f[N]是一種恰好裝滿背包的最優解。
如果並沒有要求必須把背包裝滿，而是只希望價格盡量大，初始化時應該將f[0..V]全部設為0。
為什麼呢？可以這樣理解：初始化的f數組事實上就是在沒有任何物品可以放入背包時的合法狀態。如果要求背包恰好裝滿，那麼此時只有容量為0的背包可能被價值為0的nothing「恰好裝滿」，其它容量的背包均沒有合法的解，屬於未定義的狀態，它們的值就都應該是-∞了。如果背包並非必須被裝滿，那麼任何容量的背包都有一個合法解「什麼都不裝」，這個解的價值為0，所以初始時狀態的值也就全部為0了。
【寫的偽代碼，能看懂哈。。。不懂再問好了】
E. 完全背包問題O(VN)的演算法C++源碼
#include<iostream>
usingnamespacestd;
#defineMAXN=501;
intf[MAXN];
intmain(){
intn,x,y,v;
cin>>n>>v;
for(inti=0;i<n;i++){
cin>>x>>y;
for(intj=x;j<=v;j++)
if(f[j]<f[j-x]+y)f[j]=f[j-x]+y;
}
cout<<f[v]<<endl;
return0;
}
其中n為物品種數，v為背包容量，x為物品體積，y為價值
F. 求動態規劃01背包問題c語言的代碼，要稍微簡單且無錯的。謝謝
我寫個C++的。
#include<iostream>
#define MAX 1111
using namespace std;
int f[MAX],n,m,v,w;
int main(){
cin>>n>>m;//n表示個數，m表示背包容量
for(int i=1;i<=n;++i){
cin>>v>>w;//v=價值，w=重量
for(int j=m;j>=w;--j)
if(f[j]<f[j-w]+v)
f[j]=f[j-w]+v;
}
cout<<f[m]<<'\n';
return 0;
}
C++和C應該都差不多吧。。這個最簡潔了 。順便一句，如果要能無限放的話
for(int j=m;j>=w;--j)這一句變成for(int j=w;j<=m;++j)就行了。
G. 求用A*演算法解01背包問題的C語言編的完整的源代碼，在線等，高人們幫幫我，謝謝~
這個演算法厲害。
#include "stdafx.h"
#include <iostream>
using namespace std;
#define N 7//物品數量
#define S 20//要求背包重量
int W[N+1]=;//各物品重量，W[0]不使用。。。
int knap(int s,int n)//s為剩餘重量，n為剩餘可先物品數。。
{
if(s==0)return 1;//return 1 means success..
if(s<0||(s>0&&n<1))return 0;//如果s<0或n<1則不能完成
if(knap(s-W[n],n-1))//從後往前裝，如果裝滿第n個包，剩餘的重量仍然可以在剩餘的n-1包中放下，那麼就將第n個包裝滿。
{
printf("%4d",W[n]);//列印第n個包的容量，即裝進第n個包的重量。
return 1;
}
return knap(s,n-1);//如果裝滿第n個包後，剩餘的重量不能在剩餘的n-1包中放下，那麼就不用第n個包，考慮能不能用第n-1個包。
}
void main()
{
if(knap(S,N))printf("\nOK!\n");
else printf("Failed!");
}
H. 求大神給一份C語言01背包的代碼，要每一行都有注釋，謝謝！
這是一個背包問題，該演算法已經是最簡單的了，還有遞歸演算法，我覺得更麻煩。對你的代碼進行解釋如下：
//背包問題：有m件物品和一個承重為t的背包。第i件物品的重量是w[i]，價值是v[i]。
//求解將哪些物品裝入背包可使這些物品的重量總和不超過背包承重量t，且價值總和最大。
#include<stdio.h>
#include<conio.h>
#include<string.h>
intf[1010],w[1010],v[1010];//f記錄不同承重量背包的總價值，w記錄不同物品的重量，v記錄不同物品的價值
intmax(intx,inty){//返回x,y的最大值
if(x>y)returnx;
returny;
}
intmain(){
intt,m,i,j;
memset(f,0,sizeof(f));//總價值初始化為0
scanf("%d%d",&t,&m);//輸入背包承重量t、物品的數目m
for(i=1;i<=m;i++)
scanf("%d%d",&w[i],&v[i]);//輸入m組物品的重量w[i]和價值v[i]
for(i=1;i<=m;i++){//嘗試放置每一個物品
for(j=t;j>=w[i];j--){
f[j]=max(f[j-w[i]]+v[i],f[j]);
//在放入第i個物品前後，檢驗不同j承重量背包的總價值，如果放入第i個物品後比放入前的價值提高了，則修改j承重量背包的價值，否則不變
}
}
printf("%d",f[t]);//輸出承重量為t的背包的總價值
printf(" ");
getch();
return0;
}
I. 完全背包問題，c語言編程
#include<stdio.h>
float V[1000],V1[1000];
int max(float a[],int n)
{
int s = 1;
float fmax = a[1];
for (int j=2;j<n;j++)
{
if (a[j]>fmax)
{
fmax = a[j];
a[j] = 0;
s = j;
}
}
return s;
}
int KnapSack(int n,int w[],int v[],int C)
{
int Maxvalue = 0;
int X[1000],w0[1000],w1[1000];
memset(X,0,sizeof(X));
memset(w0,0,sizeof(w0));
memset(w1,0,sizeof(w0));
for (int j=1;j<n;j++)
{
V[i] = 1.0*v[i]/w[i];
V1[i] =V[i];
}
X[1] = max(V1,n);
int w0[1] = n/w[X];
int w1[1] = n%w[X];
int k = 1;
while (w1[k++]!=0)
{
X[K] = max(V1,n);
w0[k] = w1[k]/w[Y];
w1[k] = w1[k]%w[Y];
}
for (int m=1;m<k;m++)
{
Maxvalue+=w0[m]*w[X[K]]*v[X[k];
}
return Maxvalue;
}
int main(void)
{
int s;
int w[1000];
int v[1000];
int n,i;
int C;
scanf("%d %d", &C, &n);
for(i=0;i<n;i++)
scanf("%d %d",&w[i], &v[i]);
s=KnapSack(n,w,v,C);
printf("%d",s);
return 0;
}
J. 完全背包問題，用C語言編譯的代碼~是所有代碼，不是一段關鍵代碼。
參考代碼：
/*
* n：物品種類 每種只能選取一種
* capacity：背包容量
* c[i]：第i種物品的花費 cost
* v[i]：第i種物品的價值 value
* f[j]：i狀態下容量為j時背包可獲得的最大價值
*/
int getMaxValue(int n,int capacity){
for(int i=0;i<n;i++)
for(int j=capacity;j>=0;j--)
if(i==0){
if(j>=c[i])f[j]=v[i];
else f[j]=0;
}
else if(j>=c[i])f[j]=max(f[j],f[j-c[i]]+v[i]);
return f[capacity];
}