01 背包问题

“求价值最大和”，毋庸置疑，用动态规划。此类题目属于动态规划中的一个特殊类别——“背包问题”。

PS：背包问题可以分为三种——

1.  0/1背包问题——物品只有选/不选两种状态，求最大价值和
2. 子集背包问题——分割等和子集问题
3. 完全背包问题——物品可以无限选，求可以组合成目标值的选法

设当前个数为i，当前最大背包容量为j，那么dp[i][j]表示“背包容量为j时，在前i个物品中选择的最大价值和”。有如下状态公式(设w为重量数组，v为价值数组)：

1. 如果j-w[i-1]>=0，dp[i][j] = max(dp[i-1][j-w[i-1]]+v[i-1], dp[i-1][j])
2. 如果j-w[i-1]<0，dp[i][j] = dp[i-1][j]
3. 基准1: dp[0][..]=0
4. 基准2: dp[..][0]=0

解释状态公式：

1. 如果当前背包重量减去当前物品重量后还有余地，那么当前最大价值和为“选当前物品”和“不选当前物品”两种情况的较大值
2. 如果当前背包重量减去当前物品重量后没有剩余空间了，那么当前最大价值和为“不选当前物品”的最大价值和
3. 基准1: 在物品数量为0的情况下，最大价值和永远为0
4. 基准2: 在背包容量为0的情况下，最大价值和也永远为0

//
// Created by jt on 2020/8/26.
//
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    int N, M;
    cin >> N >> M;
    vector<int> w, v;
    for (int i = 0; i < N; ++i) { int a; cin >> a; w.push_back(a); }
    for (int i = 0; i < N; ++i) { int a; cin >> a; v.push_back(a); }
    vector<vector<int>> dp(N+1, vector<int>(M+1, 0));
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            dp[i][j] = j-w[i-1] >= 0 ? max(dp[i-1][j-w[i-1]]+v[i-1], dp[i-1][j]) : dp[i-1][j];
        }
    }
    cout << dp[N][M] << endl;
}

import random
thing_number = int(input())
weight = input()
KG = input()
KG_list = [int(i) for i in KG.split(" ") if i not in [""]]
value = input()
value_list = [int(i) for i in value.split(" ") if i not in [""]]
value_max = 0
for i in range(thing_number):
    for j in range(50*thing_number*thing_number):
        value_all = 0
        weight_all = 0
        random_index = []
        while True:
            index = random.choice(range(thing_number))
            if index not in random_index:
                random_index.append(index)
            if len(random_index) == i + 1:
                break

        for r in random_index:
            weight_all += KG_list[r]
            value_all += value_list[r]
        if weight_all <= int(weight):
            if value_all > value_max:
                value_max = value_all
print(value_max)

#include <stdio.h>
#include <stdlib.h>

#define MAX(x, y)    ((x)>(y))?(x):(y)
typedef struct
{
    int weight;
    int value;
}Bagobj;

int SolveBagProb(int N, int M, Bagobj *objlist);
int SolveBagProbPlus(int N, int M, Bagobj *objlist);
int SolveBagProbPlusPlus(int N, int M, Bagobj *objlist);

int main() {
    //输入数据
    int N = 0;
    int M = 0;
    
    //1. 物品的数量
    scanf("%d", &N);
    scanf("%d", &M);

    Bagobj *objlist = (Bagobj *)malloc(sizeof(Bagobj)*N);//使用动态数组
    for(int i=0; i<N; i++)
    {
        scanf("%d", &objlist[i].weight);
    }
    for(int i=0; i<N; i++)
    {
        scanf("%d", &objlist[i].value);
    }
    
    #if 1
    //int res = SolveBagProb(N, M, objlist);
    //int res = SolveBagProbPlus(N, M, objlist);
    int res = SolveBagProbPlusPlus(N, M, objlist);
    printf("%d", res);
    #endif
}

//解决背包问题：
//所需要的数据:物品种类N，背包承重M，每种物品的重量和价值(w,v)
int SolveBagProb(int N, int M, Bagobj *objlist)
{
    //初始化一个动态规划数组，dp[N][M+1],初始化其第一行。
    //对于dp[i][j]而言：i是前i个物件，j是背包的承重(变)。
    int dp[N][M+1];
    for(int j=0; j<=M; j++)
    {
        //求价值，下面这处错误
        //dp[0][j] = (j>=objlist[0].weight)?(objlist[0].weight):(0);
        dp[0][j] = (j>=(objlist[0].weight))?(objlist[0].value):(0);
        //printf("dp[0][%d] = %d\n",j, dp[0][j]);
    }

    //对下面每一行[1, N-1],求动态规划式子
    int alt_full = 0;
    int alt_notfull = 0;
    for(int i=1; i<N; i++)
    {
        for(int j=0; j<=M; j++)
        {
            alt_full = dp[i-1][j];

            int temp_weight = objlist[i].weight;
            if(j >= temp_weight)
            {
                //alt_notfull = dp[i-1][j-temp_weight]+temp_weight;
                alt_notfull = dp[i-1][j-temp_weight]+objlist[i].value;
            }
            else {
                alt_notfull = 0;
            }
            dp[i][j] = MAX(alt_full, alt_notfull);
            //printf("dp[%d][%d] = %d\n",i,j, dp[i][j]);
        }
    }
    return dp[N-1][M];
}

int SolveBagProbPlus(int N, int M, Bagobj *objlist)
{
    //初始化一个动态规划数组，dp[N][M+1],初始化其第一行。
    //对于dp[i][j]而言：i是前i个物件，j是背包的承重(变)。
    int dp[2][M+1];
    for(int j=0; j<=M; j++)
    {
        //求价值，下面这处错误
        //dp[0][j] = (j>=objlist[0].weight)?(objlist[0].weight):(0);
        dp[0][j] = (j>=(objlist[0].weight))?(objlist[0].value):(0);
        //printf("dp[0][%d] = %d\n",j, dp[0][j]);
    }

    //对下面每一行[1, N-1],求动态规划式子
    int alt_full = 0;
    int alt_notfull = 0;
    for(int i=1; i<N; i++)
    {
        for(int j=0; j<=M; j++)
        {
            alt_full = dp[(i-1)&0x01][j];

            int temp_weight = objlist[i].weight;
            if(j >= temp_weight)
            {
                //alt_notfull = dp[i-1][j-temp_weight]+temp_weight;
                alt_notfull = dp[(i-1)&0x01][j-temp_weight]+objlist[i].value;
            }
            else {
                alt_notfull = 0;
            }
            dp[i&0x01][j] = MAX(alt_full, alt_notfull);
            //printf("dp[%d][%d] = %d\n",i,j, dp[i][j]);
        }
    }
    return dp[(N-1)&0x01][M];
}

int SolveBagProbPlusPlus(int N, int M, Bagobj *objlist)
{
    //初始化一个动态规划数组，dp[N][M+1],初始化其第一行。
    //对于dp[i][j]而言：i是前i个物件，j是背包的承重(变)。
    int dp[M+1];
    for(int j=0; j<=M; j++)
    {
        //求价值，下面这处错误
        //dp[0][j] = (j>=objlist[0].weight)?(objlist[0].weight):(0);
        dp[j] = (j>=(objlist[0].weight))?(objlist[0].value):(0);
        //printf("dp[0][%d] = %d\n",j, dp[0][j]);
    }

    //对下面每一行[1, N-1],求动态规划式子
    int alt_full = 0;
    int alt_notfull = 0;
    for(int i=1; i<N; i++)
    {
        for(int j=M; j>=0; j--)
        {
            alt_full = dp[j];

            int temp_weight = objlist[i].weight;
            if(j >= temp_weight)
            {
                //alt_notfull = dp[i-1][j-temp_weight]+temp_weight;
                alt_notfull = dp[j-temp_weight]+objlist[i].value;
            }
            else {
                alt_notfull = 0;
            }
            dp[j] = MAX(alt_full, alt_notfull);
            //printf("dp[%d][%d] = %d\n",i,j, dp[i][j]);
        }
    }
    return dp[M];
}

n=int(input())
m=int(input())
w=[int(i) for i in input().split()]
v=[int(i) for i in input().split()]

res=[[-1 for j in range(m+1)] for i in range(n+1)]
for i in range(n+1):
    res[i][0]=0
for j in range(m+1):
    res[0][j]=0

reslut=0
if n==0:
    result=0
else:
    for i in range(1,n+1,1):
        for j in range(1,m+1,1):
            if j<w[i-1]:
                res[i][j]=res[i-1][j]
            else:
                res[i][j]=max(res[i-1][j],res[i-1][j-w[i-1]]+v[i-1])
    result=res[i][j]
print(result)

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
    int i, j, N, M, weight[101] = {0}, value[101] = {0}, f[101] = {0};
    scanf("%d", &N); //物品件数
    scanf("%d", &M); //背包承重
    for(i=1;i<=N;i++){
        scanf("%d", &weight[i]);
    }
    for(i=1;i<=N;i++){
        scanf("%d", &value[i]);
    } //输入数据
    
    for(i=1;i<=N;i++){
        for(j=M;j>=weight[i];j--){ //从后向前
            f[j] = max(f[j], f[j-weight[i]]+value[i]);
        }
    }
    printf("%d", f[M]);
    return 0;
}

import java.util.*;
import java.lang.Math.*;
public class Main{
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        int[] w = new int[N];
        int[] v = new int[N];
        int[][] dp = new int[N+1][M+1];
        for(int i = 0; i < N; i++) {
            w[i] = in.nextInt();
        }
        for(int i = 0; i < N; i++) {
            v[i] = in.nextInt();
        }
        // 状态转移:  dp[i][j] 前i个物品背包容量j物品最大价值
        // 如果 w[i] > j dp[i][j] = dp[i-1][j]; 不拿
        // 如果 w[i] <= j  dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]]+v[i])
        
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= M; j++) {
                if(j - w[i-1] < 0) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]);
                }
            }
        }
        System.out.println(dp[N][M]);
        
    }
}

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int N,M;
    while(cin>>N>>M)
    {
        vector<int> v(N);
        vector<int> w(N);
        int num;
        for(int i=0;i<N;i++)
        {
            cin>>num;
            w[i]=num;
        }
        for(int i=0;i<N;i++)
        {
            cin>>num;
            v[i]=num;
        }
        int dp[N+1][M+1];
        memset(dp,0,sizeof dp);
        for(int i=1;i<=N;i++)
        {
             for(int j=w[i-1];j<=M;j++)
             {
                 dp[i][j]=dp[i-1][j];
                 dp[i][j]=max(dp[i][j],dp[i-1][j-w[i-1]]+v[i-1]);
             }
        }
        cout<<dp[N][M]<<endl;
    }
    return 0;
}

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

int knapsack(int N, int M, vector<int>& w, vector<int>& v){
    int dp[M+1];
    for(int i=0;i<=M;i++)
        dp[i] = 0;
    for(int i=1;i<=N;i++){
        for(int j=M;j>=w[i];j--){
            dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
    int ans=0;
    for(auto p:dp){
        if(p>ans){
            ans = p;
        }
    }
    return ans;
}

int main(){
    int N,M;//N件物品   M的容量
    cin>>N>>M;
    vector<int> w(N+1);//质量
    vector<int> v(N+1);//价值
    for(int i=1;i<=N;i++)
        cin>>w[i];
    for(int i=1;i<=N;i++)
        cin>>v[i];
    int ans = knapsack(N,M,w,v);
    cout<<ans;
    return 0;
}

#经典背包问题
N=int(input())
M=int(input())
w=[int(x) for x in input().split()]
v=[int(x) for x in input().split()]
dp=[[0]*(N+1) for _ in range(M+1)]
for i in range(1,M+1):
    for j in range(1,N+1):
        if w[j-1]>i:
            dp[i][j]=dp[i][j-1]
        else:
            dp[i][j]=max((dp[i-w[j-1]][j-1]+v[j-1]),(dp[i][j-1]))
print(dp[M][N])