1. 例题:NYOJ-813又见01背包

问题是求价值固定时，最小的重量

即01背包求最小

模拟一下这个用例

4 5
2 3
1 2
3 4
2 2

初始阶段

由于 min(INF,INF+a) 还是 INF,就不管，还是无穷大

第一阶段:

由第一阶段，其实就可以看出来了，为什么要初始化dp[0][0] = 0
因为j=0 是唯一的合法状态，即容量刚好是满的情况，j=0表示剩余容量为0,
而剩余容量为0，不能装东西，自然价值为0
又因为是求Min, 所以后面的合法状态，都是和 INF无穷大比，保证了其合法性。

第二阶段:

这个阶段中，有效的状态转移如上图

第三阶段:

第四阶段:

朴素版dp的代码如下:

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
using i64 = long long;

const int MAXN = 110;
const int MAXC = 1e4+10;
const int INF = 0x3f3f3f3f;
int weights[MAXN];
int values[MAXN];
i64 dp[MAXN][MAXC];
int n;
i64 cw;

int main(){
    while(cin>>n>>cw){
        int sum = 0;
        for(int i=1;i<=n;i++){
            cin>>weights[i]>>values[i];
            sum += values[i];
        }
        memset(dp,0x3f,sizeof dp);
        dp[0][0] = 0;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=sum;j++){
                dp[i][j] = dp[i-1][j];
                if(j>=values[i]){
                    dp[i][j] = min(dp[i][j],dp[i-1][j-values[i]]+weights[i]);
                }
            }
        }
        for(int j=sum;j>=0;j--){
            if(dp[n][j]<=cw){
                cout<<j<<endl;
                break;
            }
        }
    }
    return 0;
}

优化空间后的代码:
思路同求最大时一样，容量从大到小遍历就行

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
using i64 = long long;

const int MAXN = 1e4+10;
const int INF = 0x3f3f3f3f;
int weights[MAXN];
int values[MAXN];
i64 dp[MAXN];
int n;
i64 cw;

int main(){
    while(cin>>n>>cw){
        int sum = 0;
        for(int i=1;i<=n;i++){
            cin>>weights[i]>>values[i];
            sum += values[i];
        }
        memset(dp,0x3f,sizeof dp);
        dp[0] = 0;
        for(int i=1;i<=n;i++){
            for(int j=sum;j>=values[i];j--){
                dp[j] = min(dp[j],dp[j-values[i]]+weights[i]);
            }
        }
        for(int j=sum;j>=0;j--){
            if(dp[j]<=cw){
                cout<<j<<endl;
                break;
            }
        }
    }
    return 0;
}