01背包详解

一.01背包状态转移方程解析：

          原方程
              f(i,j)=max(f(i-1,j),f(i-1,j-w[i])+c[i]))

1.f(i,j)表示前i件物品放到容积为j的背包中的最大价值，w[i]表示第i件物品的重量，c[i]表示第i件物品的价值

2.一件物品最多有两种选择：放入背包或不放

3.f(i-1,j)--------i-1表示第i件物品不放入背包，j表示将i不放进背包的容积，f(i-1,j)表示不放时的最大价值

4(1).f(i-1,j-w[i])+c[i]------------表示一定将物品放入背包，此时其他物品的最大价值是f(i-1,j-w[i])（即其他i-1件物品放入j-w[i]大的空间内的最大价值）
(2).其他物品最大价值+此物品的价值==放入时的最大价值

5.(放入物品则留给其他物品的空间就会变小，其他物品的总价值也会随之变化，所以并不是当放入物品时的总价值最大)

6.比较两种可能的最大价值即是f(i,j)状态的最大价值.即max(f(i-1,j),f(i-1,j-w[i])+c[i]))
7.这时如果放入物品，则一定将该物品放下,什么意思呢？当放入这件时，为保证该物品一定能放下，便可以用作差法为该物体腾出空间即可保证可以放入

二.01背包打表模拟：

【输入样例】
         10  4      //背包容量与物品数量
         2  1       //第1件物品的重量与价值
         3  3       //第2件物品的重量与价值
         4  5       //第3件物品的重量与价值
         7 9        //第4件物品的重量与价值      

打表模拟如下图：

三.代码及解析：

#include<bits/stdc++.h>
using namespace std;
int m,n;
int w[500],c[500],a[500][500];//w为重量，c为价值，a数组为上图的f[i，j]
int main() {
    cin>>m>>n;
    for(int i=1; i<=n; i++) {
        cin>>w[i]>>c[i];
        a[0][i]=0;//将0件物品放入容量为i的包中
        a[i][0]=0;    //都放不下，总价为0
    }

   //循环解析；前i件物品放入容量为j的背包 
    for(int i=1; i<=n; i++) //所有物品考虑放或不放 
    {
        for(int j=1; j<=m; j++) {
            if(j>=w[i])//可以放入时(一定放此物品)
                a[i][j]=max(a[i-1][j],a[i-1][j-w[i]]+c[i]);
            else//放不下
            a[i][j]=a[i-1][j];//不放此物品的最大价值
        }

    }
    cout<<a[n][m];
    return 0;
}

（蒟蒻见解，如有bug请指出[举手 双手赞成]）