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]);