这个背包问题(Knapsack Problem)程序怎么写?用C语言或C++。
发布网友
发布时间：2022-05-10 05:55
我来回答
共2个回答
热心网友
时间：2023-11-08 13:29
/*
总体思路是这样的：
首先计算出单价，然后看最高单价的物品有多少个。
如果数量小于容量，则：总和+＝单价*物品数；容量＝容量－物品数；
否则：总和+＝单价*物品数；退出计算；输出总和；
其中只要容量还有，就算一下个最高单价的物品，一直重复算下去，到容量满为止。
这个计算其实挺容易，就是输入有点麻烦
希望你可以认真看看吧。
*/
#include<stdio.h>
#include<string.h>
void input(int *num,int n)
{
int i;
char ch;
fflush(stdin); //清空缓存里的数据
for(i=0;i<n;i++)
{
num[i]=0;
while(1)//只能用一个内循环一个个接收
{
scanf("%c",&ch);
if(ch==' ' || ch=='\n') break; //当碰到空格或回车就停止内循环
num[i]=num[i]*10+(ch-'0'); //否则就把原有的值剩10再加接收到的值。
}
}
}
void main()
{
int n;//物品种类
int c;//背包容量
int wi[10]; //重量
int vi[10]; //价值
double sum=0; //接收总和
double sinp[10],tmp; //单价
int i,j;
scanf("%d %d",&n,&c);
input(wi,n);//接收这里有点费事，因为接收的数据是不定的，加上又是加空格分开的
input(vi,n);//所以也挺希望有谁有更好的方法分享一下
for(i=0;i<n;i++) //求出单价
{
sinp[i]=(double)vi[i]/wi[i];
}
for(i=0;i<n;i++) //对单价从大到小排序
{
for(j=i+1;j<n;j++)
{
if(sinp[j]>sinp[i])
{
tmp=sinp[j];
sinp[j]=sinp[i];
sinp[i]=tmp;
tmp=wi[j]; //数量也交换一下，一会和单价一起计算总量时要用
wi[j]=wi[i];
wi[i]=tmp;
}
}
if(c>wi[i]) //容量比物品数量多
{
sum+=(double)sinp[i]*wi[i]; //如果上面总价（vi）也交换的话，这可以写为sum+=vi[i];
c-=wi[i];
}
else
{
sum+=(double)sinp[i]*c;
break; //容量满了，退出
}
}
printf("%.1lf\n",sum);
}
热心网友
时间：2023-11-08 13:29
就是贪心算法 每次选取单位价值最大的 如果每一种物品必选装完不能分开的话就动态规划
这个背包问题(Knapsack Problem)程序怎么写?用C语言或C++。
sinp[i]=tmp;tmp=wi[j]; //数量也交换一下，一会和单价一起计算总量时要用 wi[j]=wi[i];wi[i]=tmp;} } if(c>wi[i]) //容量比物品数量多 { sum+=(double)sinp[i]*wi[i]; //如果上面总价（vi）也交换的话，这可以写为sum+=vi[i];c-=wi[i];} else { sum+=(double)si...
计算机科学中的「背包问题(knapsackproblem)」是什么,它
零钱兑换2（Coin Change 2）问题，给定不同面额的硬币和一个总金额，计算可以凑成总金额的硬币组合数。可以转化为完全背包问题，然后再把完全背包转化为普通背包问题。背包问题（Knapsack problem）是一种组合优化的 NP 完全问题，常见于商业、组合数学、计算复杂性理论、密码学和应用数学等领域。
背包问题
void Knapsack_1(float*v,int *w,int c,float m[N+1][W+1],int *x){ Knap(v,w, c,m);Traceback(m,w,c,x);} / 以下为贪心算法解背包问题***/ void sort(float *v,float *w){ int i,j;float temp;for(i=1;i<N;i++)for(j=i+1;j<=N;j++)if(v[i]/w[i]<v[...
0-1背包问题的多种解法代码(动态规划、贪心法、回溯法、分支限界法)
void knapsack(int n,float limitw,float v[max],float w[max],int x[max]) {float c1; //c1为背包剩余可装载重量 int i; sort(n,v,w); //物品按价值密度排序 c1=limitw; for(i=1;i<=n;i++) { if(w[i]>c1)break; x[i]=1; //x[i]为1时,物品i在解中 c1=c1-w[i]; } } vo...
完全背包问题O(VN)的算法C++源码
int Knapsack(int n,int c,int w[],int v[],int x[]){ int i,j;int a[n+1][c+1];for(i=0;i<=n;i++)a[i][0]=0;//初始化第0列 for(j=0;j<=c;j++)a[0][j]=0;//初始化第0行 for(i=1;i<=n;i++)//计算第i行，进行第i次迭代 for(j=1;j<=c;j++)if...
C++有关0--1 背包问题
T Knapsack<T>:: RKnap(){ if(n>0) return f(n-1, m);else return NoAns; //NoAns可定义为类型T的一个代表无收益的常量 } // 0/1背包算法的粗略描述 void DKP(float *p, float *w, int n, float M, float &P, int *x){ S1={(0, 0)};for (i=0; i<n...
...背包问题(Knapsack Problem)是一个已证明的NP
不矛盾。背包问题(Knapsack Problem)是一个已证明的NP完全(NP-complete)问题 是指输入规模为N 时，你找不出关于N的多项式算法。我们也可以用动态规划(Dynamic Programming)方法在多项式时间内解决该问题 是在输入规模为N, V 时，我们有多项式算法。
背包问题泛化物品
费用c价值w的普通物品在背包问题中表现为：如果是01背包，其对应函数h(c)=w，其余值为0；如果是完全背包，h(v)=v/c*w（v能被c整除时）；如果是多重背包中次数最多为n的物品，h(v)=v/c*w（v被c整除且v/c<=n）。一个物品组可以视为一个泛化物品，其价值为所有费用为v的物品的最大...
背包问题多重问题
考虑一个经典的背包问题，有N种物品，每种物品最多有n件，体积为c，价值为w，背包容量为V。目标是找到一种组合，使物品体积不超过背包容量，同时价值最大。基本的解决策略类似于完全背包问题，通过动态规划求解。定义f[v]为前i种物品放入容量为v的背包的最大价值，其状态转移方程为：f[v] = max{...
完全背包问题~
设 f(x)表示重量不超过x公斤的最大价值，则 f(x）=max 当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;...
