背包问题C++已知一个载重为M的背包和n件物品，假设第i件物品的重量为wi，如果将第i件物品全部装入背包，则将获得收益p

(1) m(i,j)=max( m(i-1,j-w[i])+v[i] , m(i-1,j) , m(i-1,j-2*w[i])+2*v[i] );
(2) for (int i=0;i<=n;i++)
for (int j=0;j<=c;j++) m[i][j]=-10000;
m[0][0]=0;
for (int i=1;i<=n;i++)
for (int j=0;j<=c;j++)
{
m[i][j]=max(m[i][j],m[i-1][j]);
if (j+w[i]<=c) m[i][j+w[i]]=max(m[i][j+w[i]],m[i-1][j]+v[i]);
if (j+2*w[i]<=c) m[i][j+2*w[i]]=max(m[i][j+2*w[i]]+2*v[i]);
}(3)
取 2个 第二种物品,2个 第三种物品,获得价值最大为70

这个问题我已经解决了，但是你需要什么帮助呢？你哪个地方不明白吗？

题目要求必须恰好装满,那你就输出动态规划后求出的f[weight],如果f[weight]没被更新过,就输入no solution.
如果题目说可以不装满,就输出f[0..weight]中的最大值.
动态规划的过程：
1.枚举每种物品i
2.枚举j=weight->0,用f[ j ]+p[ i ]去更新f[ j + w[ i ] ],由于是01背包,所以要倒着枚举
有问题请追问

买2次同种饲料,两次价格不同,甲1次买1000Kg乙每次用800元 两次单价为m元y元 甲乙单价各多

先计算出每件物品的单位重量的价值是s,s即是（Ci/Wi).
然后写一个快速排序qsort,从大到小排序.
然后逐个计算添加进去即可,直到达到背包重量m即可.
记得hdu上有一道题就跟楼主的意思差不多,太久之前的,也记得不太清楚.

void 0_1_Knapsack(float w[], int n, float c,int x[]) //w[]为每个物品的重量,c为背包容量
{
int i;
for(i=1;i

因为问题存在明显无后效性和决策阶段性
所以应当使用动态规划求解
设函数f[i][j]表示前i件物品其中放入背包j件的最大价值,这样就可以实现转移了.
f[i][j]=max(f[i - 1][j - 1] + v[i], f[i - 1][j]);
两个决策表示取与不取第i件物品
初始状态为f[i][0]=0,f[0][i]=0
答案为f[n][m]
程序实现非常简单,LZ自己想想就知道了,呵呵
如果实在需要,LZ可以再问我要

（1）
将二维数组转化为一维数组之后,f[v]表示v的容量最多装多大价值.
如果顺序枚举的话,每种物品可能多次使用.例如某个物品重量为5,价值为10,那么就会用f[0]去更新f[5],用f[5]去更新f[10],最后出现f[0]=0,f[5]=10,f[10]=20的情况.而这是01背包,要求每种物品只能用一次.
逆序枚举时,是在f[5]被f[0]更新之前,就用f[5]更新f[10],这样就可以保证用一次.
（2）
首先要搞明白f[i][v]的定义：用前i种物品恰好装满一个容量为v的背包,最大价值是多少.
这句话的意思就是说,费用总和为v的状态可能没有意义.譬如说所有物品加在一起的重量都不到v,那么f[N][V]必然没有意义了.只能去找f[N][0..V]中的最大值来输出.
但是如果我们改变一下f[i][v]的定义：用前i种物品,在总重不超过v的情况下,最大价值是多少.
就可以直接输出f[N][V]了,这样只需要改变一下转移方程,加上一项f[i][v-1].
还有问题请追问.

//只是最基本的二维背包,比较好理解一点,可以有很多优化,一维也可以
#include
#define N 1001
int V[N][N],w[N],v[N];
int max(int x,int y)
{return x>y?x:y;}
int main()
{
int n,c,i,j;
scanf("%d%d",&n,&c); //n表示物体个数,c表示容量
for (i=0; i

1.排序,删掉大于S的物品.
2.编码,放入为1,不放入为0.一个编码100111…就是一种物品的选择.
3.从00000开始到11111,遍历一遍就OK了.
想用递归的话
1.排序,从小到大
2.从0000开始,如果总质量小于S,2进制序列加1,作为变量传送到下一层递归函数中
3.如果大于S,返回0
4.如果等于S,返回1以及当前的2进制序列

很明显，01是用了滚动数组的原理把二维数组简化为一维数组了，v to cost就是为了放过的物品不再重复放，你可以自己按步骤把数组没一次的改变列出来，就一目了然了。而完全背包物品时可以重复方的，所以循环与01相反，推荐你去看看背包九讲

缺少物品的价值.

w(i)=（35,30,50,60,40,10,25）
p(i)=（10,40,30,50,35,40,30）
p(i) / w(i)=( 2/7, 4/3, 3/5, 5/6, 7/8 ,4, 6/5)
x(i)=(1, 1, 0 ,0 ,1 ,1 ,1)
（求和公式）w(i)x(i0=35*1+30*1+50*0+60*0+40*1+10*1+25*1=140
(求和公式)p(i)x(i)=10*1+40*1+30*0+50*0+35*1+40*1+30*1=155
即背包的最优解是 （1, 1, 0 ,0 ,1 ,1 ,1）
最大收益是155
（大概就是这样吧,不知道有没有计算错误,自己再看一下吧）