动态规划0-1背包问题(算法实验代码)

【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《动态规划0-1背包问题(算法实验代码)》，欢迎阅读！



实验二、0-1背包问题（动态规划）

实验代码：

#include int m[20][20];

int min(int w, int c) { int temp; if (w < c) temp = w; else temp = c; return temp; }

int max(int w, int c) { int temp; if (w > c) temp = w; else temp = c; return temp; }

void knapsack(int v[], int w[], int c, int n) { int jmax = min(w[n]-1, c); for (int j = 0; j <= jmax; j++) m[n][j] = 0; for (int k= w[n]; k<= c; k++) m[n][k] = v[n]; for(int i = n-1; i > 1; i--) { jmax = min(w[i]-1, c); for(int j = 0; j <= jmax; j++) m[i][j] = m[i+1][j]; for(int k = w[i]; k <= c; k++) m[i][k] = max(m[i+1][k], m[i+1][k-w[i]]+v[i]); } m[1][c] = m[2][c]; if(c >= w[1]) m[1][c] = max(m[1][c], m[2][c-w[1]]+v[1]); }

void traceback(int x[], int w[], int c, int n) { for(int i = 1; i < n; i++) {

1 / 2






if(m[i][c] == m[i+1][c]) x[i] = 0; else { x[i]=1; c-= w[i]; } } x[n]=(m[n][c])?1:0; }

void main() { int n=20,v[20],w[20],c=19,n=20,x[150]; for(int l=0;l<150,l++) x[l]=0; for(int i=0;i<20;i++) {v[i]=i; w[i]=20-i; } knapsack (v, w, c, n); traceback(x, w, c, n); for(int j=0;j<=20;j++) { printf("0为不装包，1为装包: %d\n",x[j]); }

测试结果截图为：



2 / 2

本文来源：https://www.wddqxz.cn/12d6cdec81c758f5f61f670f.html