【文件属性】：
文件名称：算法：0-1背包问题代码
文件大小：2KB
文件格式：CPP
更新时间：2021-04-22 15:10:06
0-1背包问题
0-1背包问题算法实现
#include
using namespace std;
//---------------------------------------------------------------------------
void Knapsack(int v[],int w[],int c,int n,int m[][10]) {
int jMax = min(w[n]-1,c); //背包剩余容量上限 范围[0~w[n]-1]
for(int j=0; j<=jMax;j++) m[n][j] = 0;
for(int j=w[n];j<=c; j++) m[n][j] = v[n]; //限制范围[w[n]~c]
for(int i=n-1; i>1; i--) {
jMax = min(w[i]-1,c);
for(int j=0; j<=jMax; j++) { //背包不同剩余容量j<=jMaxc
m[i][j] = max(m[i+1][j],m[i+1][j-w[i]]+v[i]); //效益值增长vi
}
}
m[1][c] = m[2][c];
if(c>=w[1]) m[1][c] = max(m[1][c],m[2][c-w[1]]+v[1]);
}
//---------------------------------------------------------------------------
//x[]数组存储对应物品0-1向量,0不装入背包，1表示装入背包
