【模板】完全背包

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
int f[N];
int main()
{
    int n, m;
    cin >> n >> m;
    memset(f, -0x3f, sizeof(f));
    f[0] = 0;
    for(int i = 1; i <= n; i++)
    {
        int v, w;
        cin >> v >> w;
        for(int j = v; j <= m; j++)
            f[j] = max(f[j], f[j - v] + w);
    }
    int ret = 0;
    for(int i = 1; i <= m; i++)
        ret = max(ret, f[i]);
    if(f[m] < 0)
        f[m] = 0;
    cout << ret << endl;
    cout << f[m] << endl;
    return 0;
}

#include<iostream>
#include<vector>
using namespace std;
int n,V;
//无需恰好装满条件下的最大价值
void func1(vector<int>& value,vector<int>& weight)
{
    vector<int> dp(V+1); //dp[i][j]：在j容量的背包下,从前i件物品挑选，所能得到的最大价值
    dp[0]=0;
    for(int i=0;i<n;i++)
        for(int j=weight[i];j<=V;j++)//正向推
            dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
    cout<<dp[V]<<endl;
}
//需要恰好装满条件下的最大价值
void func2(vector<int>& value,vector<int>& weight)
{
    vector<int> dp(V+1);
    dp[0]=0;//容量为0的背包，恰好装满下的价值只能为0
    for(int i=1;i<=V;i++) dp[i]=-0x3f3f3f3f;//注意初始化方式的不同
    for(int i=0;i<n;i++)
        for(int j=weight[i];j<=V;j++)//正向推
            dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
    if(dp[V]<0) cout<<0<<endl;
    else cout<<dp[V]<<endl;
}
int main()
{
    cin>>n>>V;
    vector<int> value(n),weight(n);
    for(int i=0;i<n;i++) 
        cin>>weight[i]>>value[i];
    func1(value,weight);
    func2(value,weight);
    return 0;
}

#include <stdio.h>
#include <limits.h>
int max(int a, int b) {
    return (a > b ? a : b);
}
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int v[n + 1], w[n + 1], dp[n + 1][m + 1];
    v[0] = 0, w[0] = 0;
    for (int i = 0; i <= m; i++) {
        dp[0][i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        dp[i][0] = 0;
        scanf("%d %d", &v[i], &w[i]);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (j<v[i]) {
                   dp[i][j]=dp[i - 1][j];
            }
            else {
                dp[i][j] = max(dp[i - 1][j],dp[i][j-v[i]]+w[i]);
            }
            }

        }
    
    printf("%d\n", dp[n][m]);
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 0;
    }
    for (int i = 1; i <= m; i++) {
        dp[0][i] = INT_MIN;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (j<v[i]) {
                   dp[i][j]=dp[i - 1][j];
            }
            else {
                dp[i][j] = max(dp[i - 1][j],dp[i][j-v[i]]+w[i]);
            }
           
        }
    }
    printf("%d", (dp[n][m] > 0 ? dp[n][m] : 0));

    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1002;
int n, V, v[N], w[N];
int dp[N];

int main() {
    cin >> n >> V;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++)
        for (int j = v[i]; j <= V; j++) {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    cout << dp[V] << endl;

    memset(dp, -1, sizeof(dp));
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = v[i]; j <= V; j++) {
            if (dp[j - v[i]] != -1)
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    dp[V] = (dp[V] == -1) ? 0:dp[V];
    cout << dp[V] <<endl;
    return 0;
}

#include <climits>
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int dp[N];
int dp2[N];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }
    for (int i = 1; i <= m; i++) {
        dp2[i] = INT_MIN;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = v[i]; j <= m; j++) {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
            dp2[j] = max(dp2[j], dp2[j - v[i]] + w[i]);
        }
    }
    cout << dp[m] << endl;
    if(dp2[m] < 0){
        cout << 0 << endl;
    }else{
        cout << dp2[m] << endl;
    }
    return 0;
}

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

const int N = 1010;
int n, V, v[N], w[N];
int dp[N];

int main()
{
    cin >> n >> V;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i++)
        for (int j = v[i]; j <= V; j++)
            dp[j] = max(dp[j], dp[j-v[i]] + w[i]);

    cout << dp[V] << endl;

    memset(dp, 0, sizeof(dp));
    for (int j = 1; j <= V; j++)
        dp[j] = -1;

    for (int i = 1; i <= n; i++)
    {
        for (int j = v[i]; j <= V; j++)
        {
            if(dp[j-v[i]] != -1)
                dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
        }
    }
    cout << (dp[V] == -1 ? 0 : dp[V]) << endl;
    return 0;
}

#include<iostream>
#include<cstdio>
#include<climits>

using namespace std;

const int N = 1000 + 10;

int v[N], w[N], dp1[N], dp2[N];

int main(){
    int n, m;
    while(scanf("%d%d", &n, &m) != EOF){
        for(int i = 0; i < n; i++) scanf("%d%d", &w[i], &v[i]);
        fill(dp2, dp2 + m + 1, -INT_MAX);
        dp2[0] = 0;
        for(int i = 0; i < n; i++){
            for(int j = w[i]; j <= m; j++){
                dp1[j] = max(dp1[j], dp1[j - w[i]] + v[i]);
                dp2[j] = max(dp2[j], dp2[j - w[i]] + v[i]);
            }
        }
        printf("%d\n", dp1[m]);
        if(dp2[m] < 0) printf("0\n");
        else printf("%d\n", dp2[m]);
    }
    return 0;
}

import sys

# 空间复杂度使用二维数组
def ks(n, V, P, M):
    dp = [[float("-inf") for _ in range(V+1)] for _ in range(n+1)]
    for x in range(len(dp)):
        dp[x][0] = 0
#     for y in range(len(dp[0])):
#         dp[0][y] = 0
    for i in range(1, n+1):
        for j in range(1, V+1):
            if j >= P[i]:
                for k in range(0, j//P[i]+1):
                    dp[i][j] = max(dp[i][j], dp[i-1][j-k*P[i]]+k*M[i])
            else:
                dp[i][j] = dp[i-1][j]
    print(max(max(dp)))
    if dp[-1][-1] == float("-inf"):
        print(0)
    else:
        print(dp[-1][-1])
        
# 通过19/20，算法超时        
def ks_B(n, V, P, M):
    dp = [float("-inf") for _ in range(V+1)]
    dp[0] = 0
    for i in range(1, n+1):
        for j in range(V, -1, -1):
            for k in range(0, j//P[i]+1):
                dp[j] = max(dp[j], dp[j-k*P[i]]+k*M[i])
    print(max(dp))
    if dp[-1] != float("-inf"):
        print(dp[-1])
    else:
        print(0)
    return


# 满足要求
# 思考：容量序列遍历为何可以使用正向序列？而且序列的起点可以为P[i]?
# 完全背包问题，物品i没有数量限制;
# 当 j < P[i]时，容量不足以容纳物品 i，
#   相当于d[i][j] = d[i-1][j], 在O(n)复杂度的算法中也就是不更新内容，所以可以设置起点为P[i]

def ks_C(n, V, P, M):
    dp = [float("-inf") for _ in range(V+1)]
    dp[0] = 0
    for i in range(1, n+1):
        for j in range(P[i], V+1):
            dp[j] = max(dp[j], dp[j-P[i]]+M[i])
    print(max(dp))
    if dp[-1] != float("-inf"):
        print(dp[-1])
    else:
        print(0)
    return


line1 = [int(x) for x in sys.stdin.readline().split()]
n = line1[0]
V = line1[1]


P = [0]
M = [0]
for line in sys.stdin:
    tmp = [int(x) for x in line.split()]
    P.append(tmp[0])
    M.append(tmp[1])
ks_C(n, V, P, M)