01背包問題c語言

Ⅰ 01背包問題——采葯c語言

#include <stdio.h>
#include <string.h>
int f[1000+10],w[1000+10],v[1000+10] ;
int max(int x,int y)
{
if(x>y) return x;
else return y;
}
int main()
{
int t,m,i,j;
memset(f,0,sizeof(f));
scanf("%d %d",&t,&m);
for (i=1;i<=m;i++) scanf("%d %d",&w[i],&v[i]);
for (i=1;i<=m;i++){
for (j=t;j>=w[i];j--){
if(w[i]<=t)
f[j]=max(f[j-w[i]]+v[i],f[j]);
}
}
printf("%d",f[t]);
printf("\n");
}

Ⅱ c語言背包問題，求高手解答

對01背包求解，方法有回溯法、分支限界法、動態規劃法等。給你一個較容易理解的解法：窮舉搜索。問題求解的結果實際上是一個01序列，0表示該物品未裝入背包，1表示裝入背包。以本題為例，設求解結果為0111011，表示第0個和第4個未裝入，其他均裝入。關鍵就是如何找到這個01序列。設物品數量為n，則解空間為2^n，所以窮舉搜索的時間效率為O(2^n)。
#include <stdio.h>
#define N 7
int weight[N]={35, 30, 6, 50, 40 10, 25}, cost[N]={10, 40, 30, 50, 35, 40, 30};
char name[] = "ABCDEFG";
int max = 0, Max[N]; /*max用於存放最大價值，Max用於存放最優解向量*/
int v[N]; /*v：求解時用於存放求解過程向量*/
template <class T>
void Swap(T &a, T &b)
{
T tmp = a;
a = b, b = tmp;
}
void Knapsack(int step, int bag, int value1, int value2, int n)
/*step表示第step步的選擇（即第step個物品的選擇），bag為背包剩餘容量，value1表示包中現有物品總價值，value2表示剩餘物品總價值，n為物品總數量*/
{
int i;
if((step >= n) || (weight[step] > bag) || (value1 + value2 <= max)) /*如果所有物品都選擇完畢或剩餘的物品都放不進或者包中物品總價值與剩餘物品總價值之和小於等於目前的已知解，則找到一個解(但不一定是最終解或更優解)*/
{
for(i = step; i < n; i++) v[i] = 0; /*剩餘的物品都不放入*/
if(value1 > max) /*如果本次求得的解比以往的解更優，則將本次解作為更優解*/
{
max = value1;
for(i = 0; i < n; i++) Max[i] = v[i]; /*將更優解保存到Max向量中*/
}
return;
}
v[step] = 0, Knapsack(step + 1, bag, value1, value2 - cost[step], n); /*不將第step個物品放入背包，第step個物品的價值被放棄，進行下一步的選擇*/
v[step] = 1, Knapsack(step + 1, bag - weight[step], value1 + cost[step], value2 - cost[step], n); /*將第step個物品放入背包，進行下一步的選擇*/
}
void main( )
{
/*輸入數據：背包容量、物品數量、重量、價值 代碼略*/
int bag = 150, i, j, min, totalcost;
/*按物品重量從小到大的順序對物品排序，排序時cost向量中的相對順序也要作相應移動*/
for(i = 0; i < N - 1; i++) {
for(min = i, j = i + 1; j < N; j++)
if(weight[j] < weight[min]) min = j;
if(i != min) {
Swap(weight[i], weight[min]);
Swap(cost[i], cost[min]);
Swap(name[i], name[min]);
}
}
for(totalcost = 0, i = 0; i < N; i++) totalcost += cost[i]; /*求總價值*/
Knapsack(0, bag, 0, totalcost, N); /*bag為空背包容量, totalcost為物品總價值, N為物品數量*/
/*以下輸出解*/
printf("最大價值為: %d。\n裝入背包的物品依次為：\n", max);
for(i = 0; i < N; i++)
if(Max[i]) printf("%c\t", name[i]);
printf("\n");
}

我的回答你滿意嗎？如果滿意，就請採納哦，或者你也可以繼續追問。

Ⅲ 求大神給一份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;
}

Ⅳ 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;row<b_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;row<b_n;row++)
{

scanf("%f",&bx.price[row]);
}
printf("\n\n\nwithout order\n");

for(row=0;row<b_n;row++)
{

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

}
printf("\nweight:\n");
printf("\n");

for(row=0;row<b_n;row++)
{

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

}
printf("\nprice:\n");
for(row=0;row<b_n;row++)
{

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

}

for(row=0;row<b_n-1;row++)
{
maxvalue=bx.price[row]/bx.weight[row];
maxbox=row;
for(line=row+1;line<b_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;row<b_n;row++)
{

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

}
printf("\n");
printf("\nweight:\n");
for(row=0;row<b_n;row++)
{

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

}
printf("\nprice:\n");
for(row=0;row<b_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();
}
上面一點注釋都沒有 呵呵 但主要思想可以給你說一下 就是 貪心酸法 選取最高性價比的 填入 箱子；
箱子輸入所有重量 單位價格之後 排序 按照 性價比最高的 一次填入；

Ⅳ 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>

usingnamespacestd;

intmain(intargc,char*argv[])
{
intc[]={0,5,3,4,3,5};//消耗
intv[]={0,500,200,300,350,400};//value
intf[6][11];
memset(f,0,sizeof(f));//歸位0
for(inti=1;i<=(sizeof(c)/sizeof(int)-1);i++)	//i第幾個物品
{
for(intp=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]);
return0;
}

Ⅵ 求動態規劃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)就行了。

Ⅶ 編程序解決0 1 背包問題（c語言）

for (int i=1;i<=n;i++)
for (int j=0;j<=v;j++)
if (j<w[i]) f[i][j]=f[i-1][j];
else f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i]);//w為重量，c為價值，n為物品個數，v為背包容量
printf ("%d",f[n][v]);