1.动态规划法：求解决策过程的最优化
代码语言：javascript复制#include <stdio.h>
#define CAPACITY 10 //背包的容量
#define N 5 //n为物品的个数
int max(int a, int b)
{
return a > b ? a : b;
}
void print_array(int *v, int n)
{
int i;
for (i = 0; i < n; i)
{
printf("= ", v[i]);
}
printf("n");
}
int package0_1(int m[][CAPACITY 1], int *wt, int *value, int n)//n代表物品的个数
{
int i = 0; //个数
int w; //重量
/*********************************放置前0个物品*********************************/
for (w = 0; w <= CAPACITY; w )
{
m[i][w] = 0;
}
/*********************************放置1 ~ n个物品**********************************/
for(i = 1; i <= n; i )
{
for(w = 0; w <= CAPACITY; w )
{
if (wt[i - 1] <= w)
{
m[i][w] = max(value[i-1] m[i-1][w-wt[i-1]], m[i-1][w]);
}
else
{
m[i][w] = m[i-1][w];
}
}
}
return m[n][CAPACITY];
}
void answer( int *x, int m[][CAPACITY 1], int *wt, int n)
{
int w = CAPACITY; /*i = n, j= CAPACITY坐标上存放着背包容量为c时的最大价值*/
int i;
for(i = n - 1; i >= 0; i--)
{
if(m[i 1][w] == m[i][w])
{
x[i] = 0;
}
else
{
x[i] = 1; /*如果当前物品放入了背包*/
w = w - wt[i]; /*重新计算背包剩余容量，以计算在取最优时其他物品的取舍情况*/
}
}
}
int main()
{
int wt[N] = {2, 2, 6, 5, 4}; //物品的重量
int value[N] = {2, 3, 5, 4, 6}; //物品对应的价值
int m[N 1][CAPACITY 1] = {0}; //动态规划表， 行号代表选择几件放入保证，列号表示装入物品的总重量
int x[N] = {0}; //答案表，每一个物品是否放入包中
int i;
printf("The best value is: %dn", package0_1(m, wt, value, N));
for(i = 0; i <= CAPACITY; i )
{
printf("= ", i);
}
printf("n");
for(i = 0; i <= N; i )
{
print_array(m[i], CAPACITY 1);
}
answer(x, m, wt, N);
printf("The best answer is:n");
print_array(x, N);
return 0;
}2.回溯法：按选优条件向前搜索，以达到目标。 但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择
代码语言：javascript复制#include <stdio.h>
#define N 5 //物品的数量
#define C 10 //背包的容量
int w[N] = {2, 2, 6, 5, 4}; //每个物品的重量
int v[N] = {6, 3, 5, 4, 6}; //每个物品的价值
int x[N] = {0, 0, 0, 0, 0}; //x[i]=1代表物品i放入背包，0代表不放入
int cur_weight = 0; //当前放入背包的物品总重量
int cur_value = 0; //当前放入背包的物品总价值
int best_value = 0; //最优值；当前的最大价值，初始化为0
int best_x[N]; //最优解；best_x[i]=1代表物品i放入背包，0代表不放入
//t = 0 to N-1
void backtrack(int t)
{
int i;
//叶子节点，输出结果
if(t > N - 1)
{
//如果找到了一个更优的解
if(cur_value > best_value)
{
//保存更优的值和解
best_value = cur_value;
for(i = 0; i < N; i)
{
best_x[i] = x[i];
}
}
}
else
{
//遍历当前节点的子节点：0 不放入背包，1放入背包
for(i = 0; i <= 1; i)
{
x[t] = i;
if(i == 0) //不放入背包
{
backtrack(t 1);
}
else //放入背包
{
//约束条件：放的下
if((cur_weight w[t]) <= C)
{
cur_weight = w[t];
cur_value = v[t];
backtrack(t 1);
cur_weight -= w[t];
cur_value -= v[t];
}
}
}
}
}
//回溯法解决0-1背包问题
int main(int argc, char* argv[])
{
int i;
backtrack(0);
printf("最优值：%dn",best_value);
for(i = 0; i < N; i )
{
printf("%-3d", best_x[i]);
}
return 0;
}3.贪心法：每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优
代码语言：javascript复制#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct good_info
{
double price; //物品效益
double sum_price; //物品总价值
double get_rate; //获得此物品占总数的比例
int get_weight; //获得此物品的物品数量
int sum_weight; //物品总重量
}good_info;
void print_array(good_info *goods, int n);
/*********按物品效益，重量比值做序排列***************/
void insert_sort_by_price(good_info *goods, int n)
{
int i, j;
good_info tmp;
for(i = 1; i < n; i )
{
tmp = goods[i];
j = i - 1;
while ((j >= 0) && (tmp.price > goods[j].price))
{
goods[j 1] = goods[j];
j--;
}
goods[j 1] = tmp;
}
}
void bag(good_info *goods, int capacity, int n)
{
int left;
int i;
for(i = 0; i < n; i )
{
goods[i].get_weight = 0;
}
left = capacity; //背包剩余容量
for(i = 0; i < n; i )
{
if(left <= goods[i].sum_weight ) //当该物品重量大与剩余容量跳出
{
break;
}
goods[i].get_weight = goods[i].sum_weight;
goods[i].get_rate = 1.0;
left -= goods[i].sum_weight; //确定背包新的剩余容量
}
if(i < n)
{
goods[i].get_weight = left; //该物品所要放的量
goods[i].get_rate = left * 1.0 / goods[i].sum_weight;//该物品所要放的量
}
}
void print_array(good_info *goods, int n)
{
int i;
for(i = 0; i < n; i )
{
printf("%dt%lft%lft%dt%lfn",
goods[i].sum_weight,
goods[i].sum_price, goods[i].price,
goods[i].get_weight, goods[i].get_rate);
}
}
//贪心法解决背包问题
int main(int argc, char const *argv[])
{
int n = 10;
int i;
int capacity;
good_info *goods;//定义一个指针
goods = (good_info *)malloc(sizeof(good_info) * n);
if (goods == NULL)
{
printf("malloc failedn");
exit(1);
}
srand(time(NULL));
for(i = 0; i < n; i )
{
goods[i].sum_weight = rand() % 50 1;
goods[i].sum_price = rand() % 100 1;
goods[i].price = goods[i].sum_price/goods[i].sum_weight;//得出物品的重量比
}
printf("背包的最大容量：");
scanf("%d", &capacity);
insert_sort_by_price(goods, n);
bag(goods, capacity, n);
print_array(goods, n);
free(goods);
return 0;
}
