**0-1背包算法**

0-1背包算法

#include<stdio.h>
#include<stdlib.h>
#define W 6  ///物品数量
#define N 21  ///背包最大容量为20
int a[W] = { 0,2, 3, 4, 5, 9 }; ///每个物品对应的重量
int b[W][N] = { 0 };  ///存放各个容量段的能存储的最大价值
int value[W] = { 0,3, 4, 5, 8, 10 }; ///每个物品对应的价值

void beibao(){

    for (int k = 1; k < W; k++)
    {
        for (int c = 1; c < N; c++)
        {
            if (c < a[k])
            {
                b[k][c] = b[k - 1][c]; ///容量不够存放
            }
            else
            {
                int temp1 = b[k - 1][c - a[k]] + value[k];//捡起
                int temp2 = b[k - 1][c];//不捡
                b[k][c] = (temp1>temp2) ? temp1 : temp2; ///取最大价值
            }
        }
    }
}

void main()
{
    beibao();  ///进入算法
    printf("result:%d\n", b[5][20]);  ///输出容量为20的能存储的最大价值

}