首页 > 试题广场 >

【模板】01背包

[编程题]【模板】01背包
  • 热度指数：19779 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
你有一个背包，最多能容纳的体积是V。

现在有n个物品，第i个物品的体积为v_i ,价值为w_i。

（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？

输入描述:
第一行两个整数n和V，表示物品个数和背包体积。
接下来n行，每行两个数v_i和w_i，表示第i个物品的体积和价值。




输出描述:
输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。

示例1

输入

3 5
2 10
4 5
1 4

输出

14
9

说明

装第一个和第三个物品时总价值最大，但是装第二个和第三个物品可以使得背包恰好装满且总价值最大。
示例2

输入

3 8
12 6
11 8
6 8

输出

8
0

说明

装第三个物品时总价值最大但是不满，装满背包无解。

备注:
要求O(nV)的时间复杂度，O(V)空间复杂度
算法知识视频讲解
添加回答
Python 3
牛客760622808号头像 牛客760622808号
补个python的 
def ans():
    n, v = map(int, input().split(" "))
    size , worth = [0 for _ in range(n)]  , [0 for _ in range(n)]
    for i in range(n):
        size[i] , worth[i] = map(int, input().split(" "))
    
    dp1 = [0 for _ in range(v+1)]
    dp2 = [float("-inf") for _ in range(v+1)]
    dp2[0] = 0

    for i in range(n):
        for j in range(v,0,-1):
            if j >= size[i]:
                dp1[j] = max(dp1[j - size[i]] + worth[i] , dp1[j])
                dp2[j] = max(dp2[j - size[i]] + worth[i] , dp2[j])
    
    print(dp1[-1])
    res = 0 if dp2[-1] == float("-inf") else dp2[-1]
    print(res)

ans()


发表于 2021-11-03 16:55:38 回复(0)
C++
the幻云头像 the幻云 
#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=V;j>=weight[i];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=V;j>=weight[i];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;
}

发表于 2022-04-14 20:05:51 回复(1)
C++
涂比头像 涂比
为什么两种不同初始化就可以解决？

发表于 2024-03-22 10:56:45 回复(0)
牛客212561046号头像 牛客212561046号
dp+空间压缩
关于恰好装满可以这么理解：在容量为j时装第i件物品能恰好装满，那么0~i-1件物品必须恰好装满容量为j-v[i]的背包。因为初始化为负无穷，所以只有当能恰好装满时才为正数（因为初始只有dp2[0]=0, 所以当装下某件物品时背包容量为0时才会更新其为正数），装不满时就为负无穷。 
#include <climits>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, V, res=0;
    cin>>n>>V;
    vector<int> dp(V+1,0);
    vector<int> dp2(V+1, INT_MIN);
    vector<int> v(n), w(n);
    for(int i=0;i<n;i++){
        cin>>v[i]>>w[i];
    }
    dp2[0] = 0;
    for(int i=1; i<=n; i++){
        for(int j=V; j>=v[i-1]; j--){
                dp[j] = max(dp[j],dp[j-v[i-1]]+w[i-1]);
                dp2[j] = max(dp2[j],dp2[j-v[i-1]]+w[i-1]);
        }
    }

    cout<<dp[V]<<endl;

    if(dp2[V]<0){ //装不满
        cout<<0;
    }else{
        cout<<dp2[V];
    }

    return 0;   
}


编辑于 2023-12-27 18:18:06 回复(0)
C++
牛客113649850号头像 牛客113649850号 
#include<iostream>
#include<cstdio>
#include<climits>

using namespace std;

const int N = 1000 + 10;

int w[N], v[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 = m; j >= w[i]; 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;
}
发表于 2022-03-01 15:50:21 回复(0)
FakeWingCCC头像 FakeWingCCC
import Foundation

func knapsacl_full(weight: Int, items: [(Int, Int)]) -> Int {
    var dp = Array(repeating: Array(repeating: -1, count: weight + 1), count: items.count + 1)
    let n = items.count
    let w = weight

    // 必须对 i,j=0 的状态下进行初始化，这是状态的起点
    dp[0][0] = 0

    for i in 1...n {
        let weight = items[i - 1].0
        let value = items[i - 1].1
       
        // 必须正序，确保背包装满的情况
        for j in 0...w {
            dp[i][j] = dp[i-1][j]
            if j >= weight, dp[i-1][j-weight] != -1 {
                dp[i][j] = max(dp[i][j], dp[i-1][j-weight] + value)
            }
        }
    }
    return dp[n][w] == -1 ? 0 : dp[n][w]
}

func knapsack(weight: Int, items: [(Int, Int)]) -> Int {
    var dp = Array(repeating: Array(repeating: 0, count: weight + 1), count: items.count + 1)
    let n = items.count
    let w = weight

    for i in 1...n {
        let weight = items[i - 1].0
        let value = items[i - 1].1
        // 逆序防止重复计算
        for j in stride(from: w, to: 0, by: -1) {
            if j >= weight {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight] + value)
            } else {
                dp[i][j] = dp[i-1][j]
            }
        }
    }

    return dp[n][w]
}

if let input = readLine() {
    var count = 0
    var weight = 0
    var itemsArray = [(Int, Int)]()
    let parts = input.split(separator: " ")
    if parts.count == 2 {
        count = Int(parts[0])!
        weight = Int(parts[1])!
    }

    for _ in 1...count {
        if let input = readLine() {
            let parts = input.split(separator: " ")
            if parts.count == 2 {
                let w = Int(parts[0])!
                let v = Int(parts[1])!
                itemsArray.append((w, v))
            }
        }
    }

    let maxValue = knapsack(weight: weight, items: itemsArray)
    print(maxValue)
    let maxValue_fullpack = knapsacl_full(weight: weight, items: itemsArray)
    print(maxValue_fullpack)
}
发表于 2024-10-13 20:40:40 回复(0)
日刷百题头像 日刷百题
#include <iostream>
#include<vector>
using namespace std;

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

    }
    vector<int> dp1(V+1);
    vector<int> dp2(V+1);
    //初始化
    for(int j=1;j<=V;j++)
    {
        dp2[j]=-1;
    }
     
   //填表
   for(int i=1;i<=n;i++)
   {
    for(int j=V;j>=1;j--)
    {
        if(j-v[i]>=0)
        {
           dp1[j]= max(dp1[j],dp1[j-v[i]]+w[i]);
        }
         //dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    }
   }
   //dp2填表
   for(int i=1;i<=n;i++)
   {
    for(int j=V;j>=1;j--)
    {
        if(j-v[i]>=0&&dp2[j-v[i]]!=-1)
        {
            dp2[j]=max(dp2[j],dp2[j-v[i]]+w[i]);
        }
        else {
           dp2[j]=max(-1,dp2[j]);
        }
    }
   }
   cout<<dp1[V]<<endl;
   if(dp2[V]==-1)
   {
     cout<<0<<endl;
   }
    else{
         cout<<dp2[V]<<endl;
    }

}
发表于 2024-07-03 15:16:22 回复(0)
matlab
LuckyYing头像 LuckyYing 
clc 
clear

n_v_org = input('', 's');                           % 原始 输入

n_v_org = strsplit(n_v_org, ' ');                   % 拆分

n = str2double(n_v_org{1});                         % 物体 个数

T = str2double(n_v_org{2});                         % 背包 体积

prop_list = zeros(n, 2);                            % 物体 属性

for i = 1:n

    i_prop_org = input('', 's');

    i_prop_org = strsplit(i_prop_org, ' ');         % 拆分

    prop_list(i, 1) = str2double(i_prop_org{1});    % 1 物体 体积

    prop_list(i, 2) = str2double(i_prop_org{2});    % 2 物体 价值
end

prop_list;

% n = 3;                         % 物体 个数

% T = 5;                         % 背包 体积

% prop_list = [2 10
% 4 5
% 1 4];

dp_max_value = zeros(1, T+1);                       % 价值 表
dp_max_weight_value = -inf(1, T+1);                 % 价值 表
dp_max_weight_value(1) = 0;

for i = 1:n                                         % 物体 i

    i_t = prop_list(i, 1);                          % i 物体 体积

    i_v = prop_list(i, 2);                          % i 物体 价值

    for t = T+1:-1:i_t+1                            % 总 体积 t, 注意 小于 i 物体 体积 部分 不需要 计算, 加快 运行 效率
        
        if dp_max_value(1, t) < dp_max_value(1, t - i_t) + i_v
            
            dp_max_value(1, t) = dp_max_value(1, t - i_t) + i_v;
        end
        
        if dp_max_weight_value(1, t - i_t) > -1
            if dp_max_weight_value(1, t) < dp_max_weight_value(1, t - i_t) + i_v
    
                dp_max_weight_value(1, t) = dp_max_weight_value(1, t - i_t) + i_v;
            end
        end
        
        % % 上方 代码 可以 加快 计算
        % dp_max_value(1, t) = max([dp_max_value(1, t), dp_max_value(1, t - i_t) + i_v]);
        
        % if dp_max_weight_value(1, t - i_t) > -1
        %     dp_max_weight_value(1, t) = max([dp_max_weight_value(1, t), dp_max_weight_value(1, t - i_t) + i_v]);
        % end
    end
end

fprintf('%d\n%d', max(dp_max_value), max([dp_max_weight_value(T+1), 0]))

发表于 2024-01-28 19:58:07 回复(0)
C++
彪虎头像 彪虎 
#include <iostream>
#include <string.h>
using namespace std;

const int N = 1010;
int n, V, v[N], w[N];
int dp[N][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 = 1; j <= V; j++)
        {
            dp[i][j] = dp[i-1][j];
            if (j >= v[i])  
                dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]] + w[i]);
        }
    }
    cout << dp[n][V] << endl;

    // 解决第二问
    memset(dp, 0, sizeof(dp));
    for (int j = 1; j <= V; j++)
        dp[0][j] = -1;

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

    return 0;
}

发表于 2023-09-02 16:11:50 回复(0)
郝金辉2321头像 郝金辉2321 
// 手感真好，直接一次过了
import java.util.Scanner

fun main(args: Array<String>) {
    val read = Scanner(System.`in`)
    val n = read.nextInt()
    val V = read.nextInt()
    val arr1 = IntArray(n)
    val arr2 = IntArray(n)
    repeat(n) {
        arr1[it] = read.nextInt()
        arr2[it] = read.nextInt()
    }
    val res = fun1(V, arr1, arr2)
    println(res[0])
    println(res[1])
}

private fun fun1(
    V: Int, // 背包体积
    arr1: IntArray, // 体积数组
    arr2: IntArray  // 价值数组
): IntArray {
    // 简化为一维背包问题，下标为体积，数值为价值
    val dp = IntArray(V + 1)
    // 遍历物体
    for (i in arr1.indices) {
        val v = arr1[i]
        val w = arr2[i]
        // 从后向前遍历
        for (j in dp.lastIndex downTo v) {
            if (j == v || dp[j - v] != 0) {
                dp[j] = Math.max(dp[j], dp[j - v] + w)
            }
        }
        
    }
    val max = dp.max()!!
    return intArrayOf(max, dp.last())
}

发表于 2023-08-04 19:59:50 回复(0)
C
牛客831486771号头像 牛客831486771号
用例输入n=420时运行超时，有大佬能请教一下嘛😵
#include <stdio.h>
void fun(int* rra,int* rrb,int idx,int n,int v,int* ans1,int* ans2,int max){
    if(v>=0){
        *ans1=max>*ans1?max:*ans1;//背包能装的最大价值
    }
    if(v==0){
        *ans2=max>*ans2?max:*ans2;//背包恰好装满时能装的最大价值
        return;
    }
    for(int k=idx;k<n;k++){
        if(v-rra[k]>=0){
            idx=k+1;
            fun(rra,rrb,idx,n,v-rra[k],ans1,ans2,max+rrb[k]);//
        }
    }
}
int main() {
    int a, b, n, v,temp=0,ans1=0,ans2=0;
    scanf("%d %d", &n, &v);
    int rra[n],rrb[n];  
    while (scanf("%d %d", &a, &b) != EOF) { // 注意 while 处理多个 case
        // 64 位输出请用 printf("%lld") to
        if(a<=v){
            rra[temp]=a;//rra存储物品所占体积
            rrb[temp]=b;//rrb存储物体价值
            temp++;
        }
        //printf("%d\n", a + b);
    }
    fun(rra,rrb,0,temp,v,&ans1,&ans2,0);
    printf("%d\n",ans1);//输出答案一
    printf("%d\n",ans2);//输出答案二
    return 0;
}
发表于 2023-02-07 12:25:55 回复(0)
炸掉地球头像 炸掉地球 
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int dp[N];
int main() 
{
    int n, m, w, v;
    cin >> n >> m;

    memset(dp, -0x3f, sizeof(dp));
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> v >> w;
        for (int j = m; j >= v; j--)
        {
            dp[j] = max(dp[j], dp[j - v] + w);
        }
    }

    int ret = 0;
    for (int i = 1; i <= m; i++)
        ret = max(ret, dp[i]);

    if (dp[m] < 0)
        dp[m] = 0;
    cout << ret << endl;//价值最大
    cout << dp[m] << endl;//恰好装满价值最大
}

发表于 2022-11-27 17:46:21 回复(0)
Snug-XP头像 Snug-XP 
def 省空间解法():
    f1 = [0 for i in range(V + 1)]
    f2 = [-999999999 for i in range(V + 1)]
    f2[0] = 0

    for i in range(1, n + 1):
        for j in range(V, items[i][0]-1, -1):  # 注意这边要逆序
            f1[j] = max(f1[j], f1[j - items[i][0]] + items[i][1])
            f2[j] = max(f2[j], f2[j - items[i][0]] + items[i][1])
    print(f1[V])
    if f2[V] < 0:
        print(0)
    else:
        print(f2[V])


def 常规解法():
    # f1[i][j]表示背包容量为j时，前i个物品能放的最大价值
    # f2[i][j]表示背包容量为j时，前i个物品恰好放满时的最大价值
    f1 = [[0 for i in range(V + 1)] for j in range(n + 1)]
    f2 = [[0 for i in range(V + 1)] for j in range(n + 1)]
    for i in range(0, n + 1):
        for j in range(1, V + 1):
            f2[i][j] = -9999999
    for i in range(1, n + 1):
        for j in range(0, V + 1):
            if j >= items[i][0]:
                f1[i][j] = max(f1[i - 1][j], f1[i - 1][j - items[i][0]] + items[i][1])
                f2[i][j] = max(f2[i - 1][j], f2[i - 1][j - items[i][0]] + items[i][1])
            else:
                f1[i][j] = f1[i - 1][j]
                f2[i][j] = f2[i - 1][j]
    print(f1[n][V])
    if f2[n][V] < 0:
        print(0)
    else:
        print(f2[n][V])


if __name__ == "__main__":
    n, V = [int(x) for x in input().split()]
    items = [[0, 0]]
    for i in range(n):
        items.append([int(x) for x in input().split()])
    # n, V = 3, 5
    # items = [[0, 0],
    #          [2, 10],
    #          [4, 5],
    #          [1, 4]]
    # items.sort(key=lambda x: x[0])
    # 常规解法()
    省空间解法()
发表于 2022-09-16 09:21:24 回复(0)
Python3
牛客253248209号头像 牛客253248209号
# 先记录一下第一个问题的答案
n,w = map(int,input().split())
# 构造装进去
lv,lw=[],[]
for i in range(n):
    l= list(map(int,input().split()))
    lv.append(l[0])
    lw.append(l[1])
dp=[[0 for i in range(w+1)] for i in range(n+1)]
lv.insert(0,0)
lw.insert(0,0)
# 然后进行循环
for i in range(1,n+1):
    for j in range(1,w+1):
        if lv[i]<j:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-lv[i]]+lw[i])
        else:
            dp[i][j] = dp[i-1][j]
print(dp[n][w])
发表于 2022-08-23 23:25:24 回复(0)
C++
一天到晚划水的鱼头像 一天到晚划水的鱼

0-1背包模板，cpp

#include <bits/stdc++.h>

using namespace std;

// 背包最多装多大价值的物品
int getResult1(vector<int>& v, vector<int>& w, int V) {
    vector<int> dp(V + 1, 0);
    int n = v.size();
    for (int i = 0; i < n; ++i) {
        for (int j = V; j >= v[i]; --j) {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }

    return dp[V];
}

// 恰好装满背包的最大价值
int getResult2(vector<int>& v, vector<int>& w, int V) {
    vector<int> dp(V + 1, -1);
    dp[0] = 0;
    int n = v.size();

    for (int i = 0; i < n; ++i) {
        for (int j = V; j >= v[i]; --j) {
            if (dp[j - v[i]] >= 0) {
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
            }
        }
    }

    return dp[V] >= 0 ? dp[V] : 0;
}

int main() {
    int n, V;
    cin >> n >> V;

    vector<int> v(n), w(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i] >> w[i];
    }

    cout << getResult1(v, w, V) << endl;
    cout << getResult2(v, w, V) << endl;

    return 0;
}
发表于 2022-08-18 09:21:11 回复(0)
C++
土泥豆头像 土泥豆 
#include<iostream>
#include<vector>
using namespace std;
int main(){
    int weight,n,maxw=0,maxf=0;
    cin>>n>>weight;
    int w[n],v[n];
    for(int i=0;i<n;i++)
        cin>>w[i]>>v[i];
    vector<int> dp(weight+1,0);
    for(int i=0;i<n;i++)
        for(int j=weight;j>=w[i];j--)
        {
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
            maxw=max(maxw,dp[j]);
        }
    dp.assign(dp.size(),0);
    dp[0]=1;
    for(int i=0;i<n;i++)
        for(int j=weight;j>=w[i];j--)
        {
            if(dp[j-w[i]])
            {
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
            }
        }
    cout<<maxw<<endl;
    if(dp[weight]!=0)
        cout<<dp[weight]-1;
    else cout<<'0';
}

发表于 2022-08-10 20:46:26 回复(0)
C
Qofter头像 Qofter 
#include "stdio.h"
#include "stdlib.h"
// 抄榜一大佬的
int max(int a,int b)
{
    return a>b?a:b;
}

int main()
{
  int n,V; // 输入n, V
  scanf("%d%d",&n,&V);

  // 价值和重量
  int *vi=(int*)malloc(sizeof(int)*n);
  int *wi=(int*)malloc(sizeof(int)*n);
    
   for(int i=0;i<n;i++)
   { 
       scanf("%d %d",&vi[i],&wi[i]);
   }
  // dp内存
  int *dp=(int*)malloc(sizeof(int)*(V+1));
  dp[0]=0 ; // 小细节，这里不设置为0. 无法计算出正确答案

  for(int i=1;i<V+1;i++)
      dp[i]=0x80000000; // -2147483648
    
  int max_dp=0; // 第一问答案
  int j;
// 从上往下，从右往左：因为物品都只能用一次
  for(int i=1;i<=n;i++)
  {
      for(j=V;j>=vi[i-1];j--)
      {
          dp[j]=max(dp[j-vi[i-1]]+wi[i-1],dp[j]);
          if(dp[j]>max_dp) // 第一问答案就是恰好在某个容量时，可以达到的最大价值。一直记录最大值，就可以得到
            max_dp=dp[j]; // 记录更新第一问答案
      }    
  }  
  printf("%d\n",max_dp);  
  max_dp=dp[V];
 free(dp);
  if(max_dp<0)
    printf("0");
  else
    printf("%d",max_dp);       
}

发表于 2022-08-09 10:44:34 回复(0)
Python 3
神圣之风头像 神圣之风
import sys
def solution():
    input=sys.stdin.readlines()
    frst_line=[eval(i) for i in input[0].strip().split(" ")]
    num_obj,vol_total=frst_line
    data=[i.strip().split(" ") for i in input[1:]]
    for i in range(0,len(data)):
        data[i]=[eval(j) for j in data[i]]
    #构造DP矩阵
    mat=[[0 for i in range(0,vol_total+1)] for j in range(num_obj+1)]
    for i in range(1,num_obj+1):
        for j in range(0,vol_total+1):
            if(data[i-1][0]>j):
                mat[i][j]=mat[i-1][j]                #如果不能装载obj的话，就直接用上一行的值;注意是大于，不能等于
            else:
                mat[i][j]=max(mat[i-1][j],data[i-1][1]+mat[i-1][j-data[i-1][0]])
    answer1=mat[-1][-1]
    print(answer1)
    #构造DP矩阵
    mat=[[float('-inf') for i in range(0,vol_total+1)] for j in range(num_obj+1)]
    mat[0][0]=0
    for i in range(1,num_obj+1):
        for j in range(0,vol_total+1):
            if(data[i-1][0]>j):
                mat[i][j]=mat[i-1][j]                #如果不能装载obj的话，就直接用上一行的值
            else:
                mat[i][j]=max(mat[i-1][j],data[i-1][1]+mat[i-1][j-data[i-1][0]])
    answer2=mat[-1][-1] if mat[-1][-1]!=float('-inf') else 0 
    #print(mat)
    print(answer2)
solution()
发表于 2022-06-26 23:17:39 回复(0)
Java
想润的我反对画饼头像 想润的我反对画饼
import java.util.*;
public class  Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int bag = sc.nextInt();
        int[][] gift = new int[num][2];
        for (int i = 0; i < num; i++) {
            gift[i][0] = sc.nextInt();
            gift[i][1] = sc.nextInt();
        }
        System.out.println(getMaxValue(gift, bag));
        System.out.println(getfullbag(gift,bag));
    }
    private static int getMaxValue(int[][] gift, int bag ) {
        int[][] dp = new int[gift.length + 1][bag + 1];
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1 ; j < dp[0].length; j++) {
                if (j - gift[i - 1][0] >= 0 ) {
                    dp[i][j] = Math.max(dp[i - 1][j - gift[i - 1][0]] + gift[i - 1][1],
                                        dp[i - 1][j]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[gift.length][bag];
    }
    private static int getfullbag(int[][] gift, int bag) {
        int[][] dp = new int[gift.length + 1][bag + 1];
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1 ; j < dp[0].length; j++) {
                int left = j - gift[i - 1][0] ;
                if (left >= 0 ) {
                    if(left > 0){
                        if(dp[i-1][left] == 0){
                            dp[i][j] = dp[i-1][j];
                        }else{
                            dp[i][j] = Math.max(dp[i - 1][j - gift[i - 1][0]] + gift[i - 1][1],dp[i - 1][j]);
                        }
                    }else{
                        dp[i][j] = Math.max(gift[i - 1][1],dp[i - 1][j]);
                    }
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[gift.length][bag];
    }
}
发表于 2022-05-23 15:18:07 回复(0)
提交观点

问题信息

难度：
19条回答 1628浏览

热门推荐

通过挑战的用户

查看代码

相关试题

【模板】01背包

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号