读书笔记 ---- 0

/**
0-1 背包问题：经典动态规划入门题
记忆化搜索方法：静态记录下递归过程中的状态值，避免重复计算

在 n 个重量和价值分别是 wi 和 vi 的物品中挑选，使得物品重量总和
不超过 W, 并且让其价值总和尽量大

问题规模：
1 <= n <= 100
1 <= wi,vi <= 100
1 <= W <= 10000
状态转移方程：
dp(i,S) = dp(i - 1, S - w[i]) + v[i]; // S - w[i] >= 0
*/

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXW = 10000 + 5;
const int N = 100 + 5;
int n,W;
int w[N],v[N];
int d[N][MAXW];

int dp(int i, int S)
{
    int &ans = d[i][S];
    if(ans != -1) return ans;
    ans = 0;
    if(i == 0)
        return ans;
    if(S - w[i] >= 0)
        ans =max(dp(i - 1, S), dp(i - 1, S - w[i]) + v[i]);
    else
        ans =dp(i-1, S);
    return ans;
}
void solve()
{
    scanf("%d%d", &n, &W);
    for(int i = 1; i <= n ; i++)
        scanf("%d", w[i]);
    for(int i = 1; i <= n; i++)
        scanf("%d", v[i]);
    memset(d, -1, sizeof(d));
    dp(n, W);
}
int main()
{
    solve();
    return 0;
}

/**
0-1 背包问题：经典动态规划入门题

在 n 个重量和价值分别是 wi 和 vi 的物品中挑选，使得物品重量总和
不超过 W, 并且让其价值总和尽量大

问题规模：
1 <= n <= 100
1 <= wi,vi <= 100
1 <= W <= 10000
状态转移方程：
dp[i][j] = dp[i-1][j-w[i]] + v[i]; // j - w[i] >= 0
*/

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXW = 10000 + 5;
const int N = 100 + 5;
int n,W;
int w[N],v[N];
int dp[N][MAXW];

void solve()
{
    scanf("%d", &n, &W);
    for(int i = 1; i <= n ; i++)
        scanf("%d", w[i]);
    for(int i = 1; i <= n; i++)
        scanf("%d", v[i]);
    memset(d, 0, sizeof(d));
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= W; j++)
        {
            if(j < w[i])
                dp[i][j] = dp[i-1][j];
            else
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] +v[i]);
        }
    }
    printf("%d
", dp[n][W]);
}
int main()
{
    solve();
    return 0;
}

/**
在 n 种重量和价值分别是 wi 和 vi 的物品中挑选，使得物品重量总和
不超过 W, 并且让其价值总和尽量大

问题规模：
1 <= n <= 100
1 <= wi,vi <= 100
1 <= W <= 10000

0-1背包：每种物品只有一个
状态转移方程：dp[i][j] = max(dp[i-1][j] ,dp[i-1][j-w[i]]+v[i]);
0-1背包的状态更新只跟上一层的考虑有关系

完全背包：每种物品有无数个
状态转移方程：dp[i][j] = max(dp[i-1][j],dp[i][j-w[i]]+v[i]);
完全背包在本层中，需要考虑 对选择过本层物品后更新的状态 的使用，
所以在实现上有所差别
*/

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXW = 10000 + 5;
const int N = 100 + 5;
int n,W;
int w[N],v[N];
int dp[MAXW];
/**
都使用一维数组来写
*/
void solve_01()
{
    scanf("%d", &n, &W);
    for(int i = 1; i <= n ; i++)
        scanf("%d", w[i]);
    for(int i = 1; i <= n; i++)
        scanf("%d", v[i]);
    memset(d, 0, sizeof(d));
    for(int i = 1; i <= n; i++)
    {
        for(int j = W; j >= 0; j--)
        {
            //这里使用的数据都是没有更新过的上层数据
            if(j >= w[i])
                dp[j] = max(dp[j], dp[j - w[i]] +v[i]);
        }
    }
    printf("%d
", dp[n][W]);
}

void solve_entire()
{
    scanf("%d", &n, &W);
    for(int i = 1; i <= n ; i++)
        scanf("%d", w[i]);
    for(int i = 1; i <= n; i++)
        scanf("%d", v[i]);
    memset(d, 0, sizeof(d));
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= W; j++)
        {
            //这里使用的数据都是有更新过的上层数据
            if(j >= w[i])
                dp[j] = max(dp[j], dp[j - w[i]] +v[i]);
        }
    }
    printf("%d
", dp[n][W]);
}
int main()
{
    solve_01();
    return 0;
}

/**
在 n 个重量和价值分别是 wi 和 vi 的物品中挑选，使得物品重量总和
不超过 W, 并且让其价值总和尽量大

问题规模：
1 <= n <= 100
1 <= vi <= 100
1 <= wi <= 1e7
1 <= W <= 1e9

这题的重量的数量级比普通的背包扩大了10000倍，所以再使用之前的算法
枚举重量状态O(n*W),次数量到达1e11，这将不是1s可以跑出来的方法。

所以改变策略，状态描述为dp[i][j]，考虑前i个物品价值总和为j的最小重量，
状态转移方程：
dp[i][j] = min(dp[i-1][j], dp[i-1][j-v[i]]+w[i]);
然后从所有的价值状态中，找到重量合法的最大价值
*/

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXW = 1e9 + 5;
const int MAXV = 1e5 + 5;
const int N = 100 + 5;
int n,W;
int w[N],v[N];
int dp[N][MAXV];

void solve_entire()
{
    int maxv = 0;
    scanf("%d", &n, &W);
    for(int i = 1; i <= n ; i++)
        scanf("%d", w[i]);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", v[i]);
        maxv += v[i];
    }
    memset(d, 0x3f, sizeof(d));

    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= maxv; j++)
        {
            if(j < v[i])
                dp[i][j] = dp[i-1][j];
            else
                dp[i][j] = min(dp[i-1][j], dp[i-1][j-v[i]]+w[i]);
        }
    }
    int ans = maxv;
    for(int i = maxv; i >= 0; i--)
    {
        if(dp[n][j] <= W)
        {
            ans = j;
            break;
        }
    }
    printf("%d
", ans);
}
int main()
{
    solve();
    return 0;
}