01背包问题动态规划详解及C++代码.docx

0/1背包问题动态规划详解及C++代码
1 .问题描述
给定一个载重量为C的背包 有n个物品 其重量为W1价值为VI 1<=1<=11要求:把物 品装入背包 并使包内物品价值最大
在0/1背包问题中物体或者被装入背包或者0/1背包问题动态规划详解及C++代码
1 .问题描述
给定一个载重量为C的背包 有n个物品 其重量为W1价值为VI 1<=1<=11要求:把物 品装入背包 并使包内物品价值最大
在0/1背包问题中物体或者被装入背包或者不被装入背包只有两种选择。
循环变量1 J意义 前1个物品能够装入载重量为J的背包中
数组c意义c[i]|j]表示前1个物品能装入载重量为J的背包中物品的最大价值
若w[i]>j第1个物品不装入背包
否则 若w[i]<=j旦第1个物品装入背包后的价值>c[i-l][j]则记录当前最大价值 替换为 第1个物品装入背包后的价值
其C++代码如下
#iiiclude<iostieam>
using namespace std;
void KANPSACK_DP(mt c[50][50]. mt w[50], mt v[50], nit n, int C)
(
fbr(int i = 0; i v= c； i ++)
(
c[0][i] = 0;
}
fbr(int i= l;i<=n;i ++)
(
c[i][0] = 0;
for(mtj = l;j<=C;j++)
(
if(w[i] <=j)
(
+ c[i- l][j - w[i]] >c[i- l][j]) c[i][j] = v[i] + c[i - l][j - w[i]];
elsec[i][j] = c[i- l][j];
)
else c[i][j] = c[i - l][j];
)
}
void OUTPUT_SACK(int c[5O][5O], mt x[50], int w[50], int n. int C)
{
fbr(int k = n; k >= 2; k 一)
(
if(c[k][C] = c[k-l][C])
x[k] = 0;
else (
x[k] = 1;
C = C- w[k];
}
x[l] = c[l][C]?l :0;
}
hit
(
mtc[50][50];
int w[5O],v[5O];
mt x[50];
mt C,n;
coutvv”输入物品的总个数”；
cin»n;
coutvv”输入背包的