此方法限制物品重量和背包容量以及价值为整数
#include <stdio.h> #define N 50//物品数目不多于50个 #define M 1000//背包重量不多于1000 int w[N]; int v[N]; short flag[N];//标记选中的物品 int m[N][M];//记录物品价值 int GetMax(int a,int b){ return a>b?a:b; } int GetMin(int a,int b){ return a>b?b:a; } //注意:v和w从下标为0开始接收数值 void Knapsack(int n,int c) { //要求m[1][c],须得从后往前求 int jMax = GetMin(w[n-1]-1,c);//分界点 int i,j; //无法被装入背包 for(j=0;j<=jMax;j++) m[n][j] = 0; //可装入背包 for(j=w[n-1];j<=c;j++) m[n][j] = v[n-1]; //对序号为2:n-1物品进行选择 for(i=n-1;i>1;i--) { jMax = GetMin(w[i-1]-1,c);//分界点 //小于分界点即i不能被选择,有m[i][j]=m[i+1][j] for(j=0;j<=jMax;j++) m[i][j] = m[i+1][j]; //大于分界点 for(j=w[i-1];j<=c;j++) m[i][j] = GetMax(m[i+1][j],m[i+1][j-w[i-1]]+v[i-1]); } //确定最大价值,因为第一个的选择标志着选择的结束,只需确定m[1][c],所以无需设置分界点 if(w[0]<=c) m[1][c] = GetMax(m[2][c],m[2][c-w[0]]+v[0]); } void Traceback(int n,int c) { for(int i=1;i<n;i++) { if(m[i][c]==m[i+1][c]) flag[i-1] = 0;//未被选择 else{ //被选择则从总重量减去物品总量 flag[i-1] = 1; c-=w[i-1]; } } //最后一个物品单独考虑 flag[n-1] = m[n][c]?1:0; } void IsChosen(int n) { for(int i=0;i<n;i++) if(flag[i]) printf("序号:%hd,重量:%d,价值:%d ",i+1,w[i],v[i]); } int main() { int n,c; printf("背包容量:"); scanf("%d",&c); printf("物品数目:"); scanf("%d",&n); printf("依次输入物品重量:"); for(int i=0;i<n;i++) scanf("%d",&w[i]); printf("依次输入物品价值:"); for(int j=0;j<n;j++) scanf("%d",&v[j]); Knapsack(n,c); Traceback(n,c); printf("选中的物品如下: "); IsChosen(n); printf("物品最大总价值:%d ",m[1][c]); return 0; }