// 1.cpp : 定义控制台应用程序的入口点。
//
#include
"stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <
string.h>
#include <limits.h>
//0-1背包问题
//W:物体重量的序列
//V:物体的价值
//C:背包所能承受的最大重量
/*
m[i][j]:表示i个物品，背包最大承受重量为C，所能达到的最大价值
1、i=0或j=0时，m[i][j] = 0;
2、i>0,且第i个物品的重量大于j时，m[i][j] = m[i-1][j]
3、i>0，且第i个物品的重量小于等于j时，m[i][j] = max{m[i-1][j],m[i-1][j-wi]+vi}
*/
int* Knapsack(
int* W,
int* V,
int C,
int n)
{
int i,j;
int* m = (
int*)malloc(
sizeof(
int)*(n+
1)*(C+
1));
//当无物品或者背包承受力为0时
for(i=
0;i<=n;i++
)
m[i*(C+
1)] =
0;
for(j=
0;j<=C;j++
)
m[j] =
0;
//当第i个物品的重量大于j时
for(i=
1;i<=n;i++
)
{
for(j=
1;j<=C;j++
)
{
if(W[i-
1]>
j)
m[i*(C+
1)+j] = m[(i-
1)*(C+
1)+
j];
else if(m[(i-
1)*(C+
1)+j] > m[(i-
1)*(C+
1)+j-W[i-
1]]+V[i-
1])
m[i*(C+
1)+j] = m[(i-
1)*(C+
1)+
j];
else
m[i*(C+
1)+j] = m[(i-
1)*(C+
1)+j-W[i-
1]]+V[i-
1];
}
}
return m;
}
//利用记录表m得出 矢量X=<x1,x2,...,xn>,取值为0或1，0表示不放在包中。
//使得背包中所放物品最大的价值
int* build_Solution(
int* m,
int* W,
int n,
int C)
{
int i,j =
C;
int* X = (
int*)malloc(
sizeof(
int)*
n);
for(i=n;i >=
1;i--
)
{
if(m[i*(C+
1)+C] == m[(i-
1)*(C+
1)+
C])
X[i-
1] =
0;
//第i个物品不在背包中
else
{
X[i-
1] =
1;
j -= W[i-
1];
}
}
return X;
}
int main()
{
int W[] = {
2,
3,
4,
5};
int V[] = {
3,
4,
5,
7};
int C =
9;
int n =
sizeof(W)/
sizeof(
int);
//得出记录表m
int* m =
Knapsack(W,V,C,n);
//打印背包承受能力为C时的最大价值
printf(
"%d ",m[n*(C+
1)+
C]);
int* X =
build_Solution(m,W,n,C);
for(
int i=
0;i<n;i++
)
printf("%d ",X[i]);
free(m);
free(X);
return 0;
}
转载于:https://www.cnblogs.com/welsh-android-learning/p/3496294.html
