0-1背包

问题描述

有几个物品，各自有各自的重量（weight）和价值（value），现在有一个最大承重为v的背包，问此背包最多可以装的价值是多少？

• 一件物品只能放一次，可以不放
• 与放入次序无关，即数据可以是无序的
• 背包有最大承重量

• 求最大价值

  解决方法

  我们可以一件一件地放物品，那么我们只需要考虑这件物品到底该不该放入背包里，假设用dp[i , j]来表示放前i件物品（不一定这i件物品都放进去）到最大承重为j的背包时的最大价值，那么dp[i , v]就表示此背包在放前i件物品时的最大价值，我们用weight[i]表示第i件物品的重量，value[i]表示第i件物品的价值。那么我们可以状态转化方程：dp[i , j] = max{dp[i-1 , j] , dp[i-1 , j - weight[i]] + value[i]}，其中，j>=weight[i]。

• dp[i , j]表示承重量为j的背包里放前i件物品的最大价值（第i件物品不一定放进去）

• dp[i - 1 , j]表示承重量为j的背包里放前i-1件物品的最大价值。
• dp[i-1 , j - weight[i]]表示承重量为j-weight[i]的背包里放前i-1件物品的最大价值。

我们如果考虑是否要放第i件物品，由于随着背包容量的增加，背包的价值是递增的，那么我们如果要把第i件物品放入背包，就要看j-weight[i]的背包里的价值加上value[i]是否比dp[i-1 , j]（不放i物品）的价值大。

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <iomanip>
using namespace std;

int dp[100];
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int n , v;                             //总物品数和最大重量
    int value[100] , weight[100];
    cin>>n>>v;
    for(int i = 0 ; i<n ; ++i){
        cin>>weight[i]>>value[i];
    }
    for(int i = 0 ; i<n ; ++i){            //一件一件放物品
        for(int j = v ; j>=weight[i] ; --j){    //0-1背包一定要逆序更新
            dp[j] = max(dp[j] , dp[j - weight[i]] + value[i]);  //注意两个dp[j]所表示的状态不同，左边表示状态i，右边表示状态i-1
        }
    }
    for(int i = 0 ; i<=v ; ++i){
        cout<<dp[i]<<' ';
    }
}

为什么要逆序更新？？

这就涉及到状态的问题了，我们在考虑是否要放入第i件物品时，必须保证所有的背包的价值是未考虑i时的价值（即i-1的状态），而背包的价值的更新只和比它容量小的背包的价值有关，如果我们先更新小的背包，那么等到要更新大的背包时，小的背包的状态已经是状态i了，这与我们的初衷不符，所以要先把容量大的背包更新成状态i，等到更新小的背包时，大的背包的状态与它是没有关系的，所以要逆序更新。

hdu 2955 Robberies

http://acm.hdu.edu.cn/showproblem.php?pid=2955

这个题目给出抢劫每一个银行时的被捕概率和钱数，不能把概率当做weight，钱当做value来求最大钱数，因为概率是double类型，无法枚举。我们可以把钱当做weight，逃跑概率当做value，转化成求最大逃跑概率。