首页 > 试题广场 >

01 背包问题

[编程题]0/1 背包问题

热度指数：3540 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

有为N件物品，它们的重量w分别是w1,w2,...,wn，它们的价值v分别是v1,v2,...,vn，每件物品数量有且仅有一个，现在给你个承重为M的背包，求背包里装入的物品具有的价值最大总和？

输入描述:

物品数量N=5件
重量w分别是2 2 6 5 4
价值v分别是6 3 5 4 6
背包承重为M=10

输出描述:

背包内物品最大总和为15

示例1

输入

输出

算法知识视频讲解

C/C++

华科不平凡

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

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

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

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

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

解释状态公式：

如果当前背包重量减去当前物品重量后还有余地，那么当前最大价值和为“选当前物品”和“不选当前物品”两种情况的较大值
如果当前背包重量减去当前物品重量后没有剩余空间了，那么当前最大价值和为“不选当前物品”的最大价值和
基准1: 在物品数量为0的情况下，最大价值和永远为0
基准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;
}

编辑于 2020-08-26 11:14:57 回复(0)

内推荐秒回

import java.util.Scanner;

public class Main{
public static void main(String[] args){
Scanner scan=new Scanner(System.in);
int n=scan.nextInt();
int m=scan.nextInt();
int[] w =new int[n+1];
int[] v=new int[n+1];
for(int i=1; i<=n;i++){
w[i]=scan.nextInt();
}
for(int i=1; i<=n;i++){
v[i]=scan.nextInt();
}

int[] temp = new int[m + 1];
for (int i = 1; i <=n; i++) {
for (int j = m; j >0 ; j--) {
if (j >= w[i]){
temp[j] = Math.max(temp[j], temp[j-w[i]] + v[i]);
}
}
}
System.out.println(temp[m]);

}
}

发表于 2020-07-28 21:35:24 回复(0)

Java

湮灭丶星空

经典01背包模板题(JAVA实现)

使用动态规划


import java.util.Scanner;
 public class Main {
    static int w[];
    static int v[];
    static int dp[];
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int N=scanner.nextInt();
        w=new int[N];
        v=new int[N];
        int C=scanner.nextInt();
        dp=new int[C+1];
        for (int i = 0; i < N; i++) {
            w[i]=scanner.nextInt();
        }
        for (int i = 0; i < N; i++) {
            v[i]=scanner.nextInt();
        }
        for (int i = 0; i < N; i++) {   //物品
            for (int j = C; j >=w[i]; j--) {   //容量
                dp[j]=Math.max(dp[j],dp[j-w[i]]+v[i]);
            }
        }
        System.out.println(dp[C]);
    }
}

使用递归+记忆化数组

import java.util.Scanner;

public class Main {
    static int N;
    static int W;
    static int w[];
    static int v[];
    static int a[][];
    static int dfs(int index,int C){  //C 表示当前容量
        if(index>N)return 0;
        if(C<0)return 0;
        if(a[index][C]!=0)return a[index][C];
        if(C-w[index]<0) {

            a[index][C]= dfs(index + 1, C);
        }else {
            a[index][C]= Math.max(v[index] + dfs(index + 1, C - w[index]), dfs(index + 1, C));
        }
        return a[index][C];
    }
    public static void main(String[] args) {
        Scanner reader=new Scanner(System.in);
        N= reader.nextInt();
        W= reader.nextInt();
        w=new int[N+1];
        v=new int[N+1];
        a=new int[N+1][W+1];
        for (int i = 0; i < N; i++) {
            w[i]= reader.nextInt();
        }
        for (int i = 0; i < N; i++) {
            v[i]= reader.nextInt();
        }
        System.out.println(dfs(0,W));
    }

}

发表于 2021-04-20 23:42:23 回复(0)

冲B保M

动态规划好难，贴一个回溯法的代码吧，挨个枚举简单粗暴。

import java.util.*;
 
public class Main {
    static  int maxValue = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int N = sc.nextInt();
            int M = sc.nextInt();
            int[] w = new int[N];
            int[] v = new int[N];
            for (int i = 0; i < N; i++) {
                w[i] = sc.nextInt();
            }
            for (int i = 0; i < N; i++) {
                v[i] = sc.nextInt();
            }
            dfs(w,v,M,0,N,0);
            System.out.println(maxValue);
        }
    }
    public static void dfs(int[] w, int[] v, int m, int start, int N,int value) {
        // 剪枝，当m<=0 不能装了，就不用挨个比较了
        if (m <= 0) {
            return;
        }
        for (int i = start; i < N; i++) {
            // 如果背包容量还够，就装进去
            if (m - w[i] >= 0) {
                value += v[i];
                if (value > maxValue) {
                    maxValue = value;
                }
                m = m - w[i];
                // 在第一个装的基础上，看看后面的装不装
                dfs(w,v,m,i+1,N,value);
                // 回溯，第一个不装，下一轮for循环就会考虑装不装第二个了
                value -= v[i];
                m += w[i];
            }
        }
    }
}

发表于 2020-10-22 16:05:15 回复(0)

酷宝向前冲

0-1 背包

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] w = new int[N];
        for(int i = 0; i < N; i++) {
            w[i] = sc.nextInt();
        }
        int[] v = new int[N];
        for(int i = 0; i < N; i++) {
            v[i] = sc.nextInt();
        }
        System.out.println(knapsack(M, N, w, v));                
    }
    
    public static int knapsack(int M, int N, int[] w, int[] v) {
        int[][] dp = new int[N+1][M+1];
        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-w[i-1]] + v[i-1], dp[i-1][j]); // 装和不装
                }
            }
        }
        return dp[N][M];
    }
    
}

发表于 2020-08-13 15:04:44 回复(0)

赶不上高铁的查查

JS解法

const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
})

let lines = []
let p = new Promise((resolve, reject)=>{
    rl.on('line', function(line){
        lines.push(line)
        lines.length === 4 && resolve(lines)
    })
})

p.then(data => {
     let N = parseInt(lines[0]) // 物品数量
     let M = parseInt(lines[1]) // 背包承重量
     let w = lines[2].split(' ').map(x => parseInt(x)) // 重量数组
     let v = lines[3].split(' ').map(x => parseInt(x)) // 价值价值数组
     
     // 开始dp
     // dp中存放某重量对应的最大价值
     // 状态转移方程 ：dp[j] = Max{dp[j], dp[j - w[i]] + v[i]}
     // 等式左边dp[j] : j公斤重量对应的最大价值（待计算）
     // 等式右边dp[j] : j公斤重量对应的最大价值（之前计算的，不包含i物品）
     // dp[j - w[i]] + v[i] : 挑选i物品来凑j公斤时能得到的最大价值
     let dp = new Array(M + 1).fill(0)
     for(let i = 0; i < N; i++){
         for(let j = M; j >= w[i]; j--){
             dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i])
         }
     }
    
     // 输出结果(打印)
     console.log(dp[M])
     
}, err => {
    throw err
})

牛客编程题中JS读取输入流与输出结果的方式

const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
})

// 输入缓存
let lines = [] 

let p = new Promise((resolve, reject)=>{
    // 监听输入，遇到回车调用回调函数
    // 回车前的输入流以字符串的形式存放在line中
    rl.on('line', function(line){
        lines.push(line)
        
        // ... 
        
        // 判断输入是否结束, 若结束则调用resolve
        lines.length > 7 && resolve(lines)
    })
})

p.then(data => {
     // data是resolve回调中传入的lines
    
     // ... 
      
     // 输出流，打印结果
     console.log()
}, err => {
    throw err
})

发表于 2020-08-05 16:42:46 回复(0)

给孝文一个offer吧

importjava.util.Scanner;

publicclassMain {

privatestaticScanner sc;

publicstaticvoidmain(String[] args) {

sc = newScanner(System.in);

intnum = sc.nextInt();

intbag = sc.nextInt();

int[] w = newint[num+1];

int[] v = newint[num+1];

w[0] = 0;

v[0] = 0;

for(inti = 1; i <= num; i++)

w[i] = sc.nextInt();

for(inti = 1; i <= num; i++)

v[i] = sc.nextInt();

int[][] f = newint[num+1][bag+1];

for(inti = 0; i <= num; i++) {

for(intj = 0; j <= bag; j++) {

if(i == 0|| j == 0)

f[i][j] = 0;

else{

f[i][j] = f[i-1][j];

if(j >= w[i])

f[i][j] = Math.max(f[i-1][j], v[i] + f[i-1][j-w[i]]);

}

System.out.println(f[num][bag]);

}

发表于 2020-03-10 21:57:17 回复(0)

我来自哪里

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)

发表于 2020-02-26 13:25:09 回复(0)

C/C++

笨ben

#include <iostream>

#include<algorithm>

#include<vector>

using namespace std;

class Solution

{

public:

int knapsack(int* v, int* w, int c, int n, int** m)

{

int jmax = min(w[n - 1] - 1, c);

for (int j = 0; j <= jmax; j++)

{

m[n][j] = 0;

}

for (int j = w[n - 1]; j <= c; j++)

{

m[n][j] = v[n - 1];

}

for (int i = n - 1; i >= 1; i--)

{

int jmaxs = min(w[i - 1] - 1, c);

for (int j = 0; j <= jmaxs; j++)

{

m[i][j] = m[i + 1][j];

}

for (int j = w[i - 1]; j <= c; j++)

{

m[i][j] = max(m[i + 1][j], m[i + 1][j - w[i - 1]] + v[i - 1]);

}

m[1][c] = m[2][c];

if (c >= w[0])

{

m[1][c] = max(m[1][c], m[2][c - w[0]] + v[0]);

}

return m[1][c];

}

};

int main() {

int n;

cin >> n;

int c;

cin >> c;

int* w = new int[n];

int* v = new int[n];

int** m = new int*[n + 1];

for (int i = 0; i <= n; ++i) {

m[i] = new int[c + 1];

}

for (int i = 0; i < n; i++) {

int num;

cin >> num;

w[i] = num;

}

for (int i = 0; i < n; i++) {

int num1;

cin >> num1;

v[i] = num1;

}

Solution a;

int result = a.knapsack(v, w, c, n, m);

cout << result << endl;

// Free the allocated memory

delete[] w;

delete[] v;

for (int i = 0; i <= n; ++i) {

delete[] m[i];

}

delete[] m;

return 0;

}

编辑于 2023-12-26 21:36:38 回复(0)

C/C++

听说改名字就有offer

来个C++版本

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

int main() {
    int N;
    int M;
    cin>>N;
    cin>>M;
    vector<int> w(N);
    vector<int> v(N);
    vector<int> f(M+1,0);
    for(int i=0;i<N;++i) cin>>w[i];
    for(int i=0;i<N;++i) cin>>v[i];

    for(int i=1;i<=N;++i){
        int x = w[i-1];
        for(int j=M;j>=x;--j){
            f[j] = max(f[j],f[j-x]+v[i-1]);
        }
    }
    cout << f[M]<<endl;
    return 0;
}
// 64 位输出请用 printf("%lld")

发表于 2024-08-15 19:42:25 回复(0)

C/C++

优秀的社畜爱读书

#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];
}

编辑于 2023-12-19 22:07:14 回复(0)

珊珊可爱

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)

发表于 2021-06-20 12:34:58 回复(0)

DoubleBean1

#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;
}

发表于 2020-12-19 00:18:28 回复(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]);
        
    }
}

发表于 2020-09-04 15:41:44 回复(0)

露西恩缇努维尔

#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;
}

发表于 2020-09-03 16:48:30 回复(0)

Jelly_96

动态规划01背包问题，优化版

n = int(input())
w = int(input())
weights = list(map(int,input().split()))
value = list(map(int,input().split()))

dp = [0]*(w+1) #面对第i个物品，背包容量为j时的价值最大值
for i in range(1,n+1):
    for j in range(w,weights[i-1]-1,-1):
        dp[j] = max(dp[j-weights[i-1]]+value[i-1],dp[j])

print(dp[-1])

发表于 2020-08-05 15:17:11 回复(0)

无辄_

//标准01背包
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        //开启对数据进行接收处理
        Scanner scanner = newScanner(System.in);
        //物品的数量
        intN = scanner.nextInt();
        //背包的容量
        intW = scanner.nextInt();
        //建立物品的体积数组
        int[] weight = newint[N + 1];
        //建立物品的价值数组
        int[] value = newint[N + 1];
         
        //开始接收数据
        //表示第i组数据的重量和价值
        for(inti = 1;i <= N;i++){
            weight[i] = scanner.nextInt();
        }
        for(inti = 1;i <= N;i++){
            value[i] = scanner.nextInt();
        }
        scanner.close();
         
        //开始干活
        int[] dp = newint[W + 1];
        dp[0] = 0;
        for(inti = 1;i <= N;i++){
            for(intj = W;j >= weight[i];j--){
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        System.out.println(dp[W]);
    }
     
}

发表于 2020-07-27 15:09:34 回复(0)

牛客492718852号

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

int MaxBenefit(int num, int M, int * wi, int * vi);

int main(void)
{
    int i;
    int num;
    int M;
    int value;


    int * wi = new int(num);
    int * vi = new int(num);

    cin >> num;
    if (num < 1)
    {
        cout << 0 << endl;
        return 0;
    }
    cin >> M;
    if (M <= 0)
    {
        cout << 0 << endl;
        return 0;
    }
    for (i = 0; i < num; i++)
    {
        cin >> wi[i];
    }
    for (i = 0; i < num; i++)
    {
        cin >> vi[i];
    }

    value = MaxBenefit(num, M, wi, vi);
    cout << value << endl;
}

int MaxBenefit(int num, int M, int * wi, int * vi)
{
    int i;
    int j;
    vector<vector<int> > f(num, vector<int>(M + 1, 0)); //全部初始化为 0 了

    for (j = 0; j <= M; j++)
    {
        if (wi[0] <= j)
            f[0][j] = vi[0]; //装得下就装有比没有要好
    }
    for (i = 1; i < num; i++) //物体的个数
    {
        for (j = 1; j <= M; j++) //背包的剩余容量
        {
            if (wi[i] <= j)
                f[i][j] = max(f[i - 1][j], f[i - 1][j - wi[i]] + vi[i]); //容量足够
            else
                f[i][j] = f[i - 1][j];
        }
    }
    return f[num - 1][M];
}

发表于 2020-07-24 20:52:04 回复(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;
}

发表于 2020-07-18 21:08:54 回复(0)

songtt

动态规划-01背包问题

n = int(input())
w = int(input())
w_list = [int(x) for x in input().split()]
v_list = [int(x) for x in input().split()]
def solution():
    # dp[i][j]: 前i个物品且当前背包的容量为j时的最大价值
    dp = [[0]*(w+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, w+1):
            dp[i][j] = dp[i-1][j]
            if j >= w_list[i-1]: # max(不选物品i, 选物品i)
                dp[i][j] = max(dp[i-1][j], 
                               dp[i-1][j-w_list[i-1]]+v_list[i-1])
    return dp[n][w]
print(solution())

编辑于 2020-07-18 19:29:52 回复(0)