c語言01背包問題,01背包問題c++實現

本文目錄一覽：

• 1、求大神給一份C語言01背包的代碼，要每一行都有注釋，謝謝！
• 2、c語言01背包問題動態規划出錯。麻煩各位幫忙糾錯一下，謝謝
• 3、c語言0-1背包問題高手進來
• 4、01背包問題-動態規劃 整理成C語言！謝謝！
• 5、背包問題C語言簡短代碼，大神們最好帶解釋和注釋，謝謝！！！

求大神給一份C語言01背包的代碼，要每一行都有注釋，謝謝！

這是一個背包問題，該算法已經是最簡單的了，還有遞歸算法，我覺得更麻煩。對你的代碼進行解釋如下：

//背包問題：有m件物品和一個承重為t的背包。第i件物品的重量是w[i]，價值是v[i]。

//求解將哪些物品裝入背包可使這些物品的重量總和不超過背包承重量t，且價值總和最大。

#include stdio.h

#include conio.h

#include string.h

int f[1010],w[1010],v[1010];//f記錄不同承重量背包的總價值，w記錄不同物品的重量，v記錄不同物品的價值

int max(int x,int y){//返回x,y的最大值

    if(xy) return x;

    return y;

}

int main(){

    int t,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(“\n”);

    getch();

    return 0;

}

c語言01背包問題動態規划出錯。麻煩各位幫忙糾錯一下，謝謝

你這是完全背包。01背包每個物品只能裝一次，因此必須和上一個物品比較，否則會出現重複裝的情況。

f[i][j]表示把前i個物品裝入容量為j的箱子能得到的最大價值

則有：

f[i][j]=max(f[i-1][j]/*不裝*/,f[i-1][j-c]+v/*裝，但必須滿足j=c*/)

改好的代碼如下所示：

#include algorithm

#include iostream

#include string.h

using namespace std;

int main(int argc, char *argv[])

{

    int c[] = {0,5,3,4,3,5};//消耗

    int v[] = {0,500,200,300,350,400}; // value

    int f[6][11];

    memset(f,0,sizeof(f)); //歸位0

    for(int i = 1; i = (sizeof(c)/sizeof(int) – 1); i++)  //i 第幾個物品

    {

        for(int p = 1; p = 10; p++) //表示10 個空間

        {

            if(p  c[i])

            {

                f[i][p] = f[i][p – 1];

            }

            else

            {

//              f[i][p] = max(f[i – 1][p], f[i][p – c[i]] + v[i]);

f[i][p] = max(f[i – 1][p], f[i – 1][p – c[i]] + v[i]);

            }

        }

    }

    printf(“%d”,f[5][10]);

    return 0;

}

c語言0-1背包問題高手進來

#include “stdio.h”

#include “time.h”

#define BOXMAX 10

typedef struct BOX

{

int locate[BOXMAX];

float weight[BOXMAX];

float price[BOXMAX];

int n;

}box;

void main()

{

box bx;

int sign=0;

int row,line;

int maxbox;

int tmp;

float maxvalue=0;

int b_n;

float input;

float b_total;

float gotcount=0;

srand(time(NULL));

while(!sign)

{

printf(“input the number of bpx:”);

scanf(“%d”,b_n);

printf(“\nintput the weight of box:”);

scanf(“%f”,b_total);

if(b_n=BOXMAX)

{

sign=1;

}

}

printf(“\ninput the weight:”);

for(row=0;rowb_n;row++)

{

/*

bx.locate[row]=row+1;

bx.weight[row]=rand()%10+1;

bx.price[row]=rand()%10+1;

*/

bx.locate[row]=row+1;

scanf(“%f”,bx.weight[row]);

}

printf(“\ninput the price:”);

for(row=0;rowb_n;row++)

{

scanf(“%f”,bx.price[row]);

}

printf(“\n\n\nwithout order\n”);

for(row=0;rowb_n;row++)

{

printf(“%4d”,(int)bx.locate[row]);

}

printf(“\nweight:\n”);

printf(“\n”);

for(row=0;rowb_n;row++)

{

printf(“%4d”,(int)bx.weight[row]);

}

printf(“\nprice:\n”);

for(row=0;rowb_n;row++)

{

printf(“%4d”,(int)bx.price[row]);

}

for(row=0;rowb_n-1;row++)

{

maxvalue=bx.price[row]/bx.weight[row];

maxbox=row;

for(line=row+1;lineb_n;line++)

{

if((bx.price[line]/bx.weight[line])maxvalue)

{

maxvalue=bx.price[line]/bx.weight[line];

maxbox=line;

}

}

if(maxbox!=row)

{

tmp=bx.weight[row];

bx.weight[row]=bx.weight[maxbox];

bx.weight[maxbox]=tmp;

tmp=bx.price[row];

bx.price[row]=bx.price[maxbox];

bx.price[maxbox]=tmp;

tmp=bx.locate[row];

bx.locate[row]=bx.locate[maxbox];

bx.locate[maxbox]=tmp;

}

}

printf(“\n\n\nlist order\n”);

for(row=0;rowb_n;row++)

{

printf(“%4d”,(int)bx.locate[row]);

}

printf(“\n”);

printf(“\nweight:\n”);

for(row=0;rowb_n;row++)

{

printf(“%4d”,(int)bx.weight[row]);

}

printf(“\nprice:\n”);

for(row=0;rowb_n;row++)

{

printf(“%4d”,(int)bx.price[row]);

}

row=0;

while(b_total=bx.weight[row])

{

b_total=b_total-bx.weight[row];

gotcount+=bx.price[row];

row+=1;;

}

getcount+=(b_total/bx.weight[row])*bx.price[row];

printf(“\n\n%d”,(int)gotcount);

getch();

getch();

}

上面一點注釋都沒有 呵呵 但主要思想可以給你說一下 就是 貪心酸法 選取最高性價比的 填入 箱子；

箱子輸入所有重量 單位價格之後 排序 按照 性價比最高的 一次填入；

01背包問題-動態規劃 整理成C語言！謝謝！

#includestdio.h

#includestdlib.h

int c[50][50];

int w[10],v[10];

int x[10];

int n;

void KNAPSACK_DP(int n,int W);

void OUTPUT_SACK(int c[50][50],int k) ;

void KNAPSACK_DP(int n,int W)

{

int i,k;

for(k=0;k=W;k++)

c[0][k]=0;

for(i=1;i=n;i++)

{

c[i][0]=0;

for(k=1;k=W;k++)

{

if(w[i]=k)

{

if(v[i]+c[i-1][k-w[i]]c[i-1][k])

c[i][k]=v[i]+c[i-1][k-w[i]];

else

c[i][k]=c[i-1][k];

}

else

c[i][k]=c[i-1][k];

}

}

}

void OUTPUT_SACK(int c[50][50],int k)

{

int i;

for(i=n;i=2;i–)

{

if(c[i][k]==c[i-1][k])

x[i]=0;

else

{

x[i]=1;

k=k-w[i];

}

}

x[1]=(c[1][k]?1:0);

for(i=1;i=n;i++)

printf(“%4d”,x[i]);

}

void main()

{

int m;

int i,j,k;

printf(“輸入物品個數:”);

scanf(“%d”,n);

printf(“依次輸入物品的重量:\n”);

for(i=1;i=n;i++)

scanf(“%d”,w[i]);

printf(“依次輸入物品的價值:\n”);

for(i=1;i=n;i++)

scanf(“%d”,v[i]);

printf(“輸入背包最大容量:\n”);

scanf(“%d”,m);

for(i=1;i=m;i++)

printf(“%4d”,i);

printf(“\n”);

KNAPSACK_DP(n,m);

printf(“構造最優解過程如下:\n”);

for(j=1;j=5;j++)

{

for(k=1;k=m;k++)

printf(“%4d”,c[j][k]);

printf(“\n”);

}

printf(“最優解為:\n”);

OUTPUT_SACK(c,m);

system(“pause”);

}

背包問題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了。

【寫的偽代碼，能看懂哈。。。不懂再問好了】