背包精讲之——01背包

 

了解01背包时应该注意01背包在问法上的差别：

    初始化分两种情况  

     (1)、如果背包要求正好装满则初始化 f[0] = 0, f[1~w] = -INF;  

      (2)、如果不需要正好装满 f[0~v] = 0;

 

 

 

 题目

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

    

整体思路：

背包问题一直是困扰自己的一块，今天开始着手整理背包问题，第一种—01背包不但是最简单的动规问题，更是最简单的背包问题，但是还是一个开始

背包问题其实就是用体积作为遍历对象，对所有的物品的体积遍历，在V--的同时看是否能够盛下，如果能够，就在将剩下的体积所能盛下的最大值加到当前的体积所记录的价值，循环，知道最后直接输出V所对应的价值就是最优解。

其实在理解本算法的时候，直接单纯的想是很难理解的，本人看来还是需要举一下实例，通过模拟算法的过程来理解本算法，在理解其大概之后再变化理解其精髓

 

 

解法一： 

 状态方程：   f[v]=max{f[v],f[v-c[i]]+w[i]};

简单一维数组

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
int main()
{
    int T,N,V;//T为测试数据个数 N为物品个数  V为背包所容纳的体积
    int f[1001],vol[1001],val[1001] ,tem;//f记录i体积下的能盛下的最大价值    vol[i] 第i件物品的体积  val[i]记录第i件物品的价值
    scanf("%d",&T);


    while(T--)
    {
        int i,j;
        scanf("%d %d",&N,&V);
        for(i = 0 ; i < N ; i++)
        scanf("%d%d",&vol[i],&val[i]);
        memset(f,0,sizeof(f));
        for(i = 0 ; i < N ; i++)  //便利i件物品
        {
            for(j = V ; j >= vol[i]; j--)
            {
                tem = f[  j-vol[i]  ] + val[i];
                if( f[j] < tem )
                f[j] = tem;
            }
        }
        cout<<f[V]<<endl;
    }
    return 0;
}

 

解法二

使用二维数组，，，未完待续