C语言那个背包问题的算法。要口述。不要复制的。

如题所述

推荐答案 2014-02-11

就是用二维状态F[i][j]表示当前的最大价值，i为第几个东西，j为背包大小，对于第i个物品有价值v[i]j，和大小s[i]，那么转移方程为f[i][n] = max(f[i-1][n-s[i]] + v[i],f[i][n]) 如果是物品只有一个对于每个i你就从背包大小n for到0就可以了，这里需要保证n-s[i] >= 0。如果是物品无穷多那么从0for到n就可以了。。
纯手打。。追问

怎么查找的。算法啊

我就是看不懂转移方程

用白话解释一下方程啊

额额

追答

就是对于第i个物品，当前如果总共占j个空间，那么可能不选这个物品，从之前i-1个物品时就已经占了j个空间，或者选这个物品，那么i-1个物品时占了j-s[i]个空间。其实背包问题就是个枚举，只不过稍微聪明了一下，存了一下之前枚举过的大小的最优解，当后面一个物品要用这个状态时直接给出之前求出的部分。楼主可以学一下记忆化搜索，其实就是这种思想的。

追问

射了

谢了

温馨提示：答案为网友推荐，仅供参考

当前网址：http://88.wendadaohang.com/zd/VMKSc11aaaaB1BttgV.html

相似回答

C语言算法求助:背包问题答：//如果每种商品只有一件，是0-1背包问题读入的数据N代表物品个数 V代表背包容量。//对于你的例子，输入为 //5 16 //2 3 //3 2 //4 3 //5 7 //6 9 //输出为21 include <iostream> using namespace std;define MAXSIZE 1000 int f[MAXSIZE + 1],c[MAXSIZE + 1],w[MAXSIZE...

c语言背包问题答：1、将各个物品按照单位价值由高到低排序；2、取价值最高者放入背包；3、计算背包的剩余空间；4、重复2-3步，直到背包剩余容量=0或者物品全部装入背包为止（对于0-1背包，终止条件为背包剩余容量无法装入任意一件物品或者物品全部装入背包）。include<stdio.h> void package(int n,float c,float v[],...

背包问题,C语言编程答：赋值a=a+m[++i]，比较b和b+s[++i]的大小，赋值b=b+s[++i]（理论上，物品价值总该是为正的吧，若是这样的话，不用比较大小了，直接赋新值，直到跳出第一轮循环为止；另外有一种设想，若价值全为正，

C语言那个背包问题的算法。要口述。不要复制的。答：就是用二维状态F[i][j]表示当前的最大价值，i为第几个东西，j为背包大小，对于第i个物品有价值v[i]j，和大小s[i]，那么转移方程为f[i][n] = max(f[i-1][n-s[i]] + v[i],f[i][n]) 如果是物品只有一个对于每个i你就从背包大小n for到0就可以了，这里需要保证n-s[i] >= ...

用C语言实现背包问题求解。答：printf("请输入背包能装入的总体积：");scanf("%d",&totalvol);printf("请输入物品件数：");scanf("%d",&n);printf("请输入每件物品的体积：");for(i=0;i<n;i++)scanf("%d",&w[i]);while(s.top!=-1){ if(sum+w[j]<=totalvol){ Push(s,j);sum+=w[j];} if(sum=...

c语言01背包问题谁能简单说下答：01背包问题就是有个容量为W的包，然后有一堆的物品(1...n)，其中wi、vi分别为第i个物品的重量和价值，现在需要求的就是使得包中所装的物品尽可能的价值高。那么这个物品放不放在包中对应取值0 or 1。其算法为动态规划，需要证明最优子结构性质。用s[i][j]表示只有前i个物品且包容量为j时所...

完全背包问题(C语言,pascal)答：每件的价值分别为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...

这个背包问题(Knapsack Problem)程序怎么写?用C语言或C++。答：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);//所以也挺希望有谁有更好...

大家正在搜