首页 > 试题广场 >

01背包

[编程题]01背包

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

现有一个容量大小为V的背包和N件物品，每件物品有两个属性，体积和价值，请问这个背包最多能装价值为多少的物品？

输入描述:

第一行两个整数V和n。
接下来n行，每行两个整数体积和价值。1≤N≤1000,1≤V≤20000。
每件物品的体积和价值范围在[1,500]。

输出描述:

输出背包最多能装的物品价值。

示例1

输入

输出

算法知识视频讲解

craboo-oo-oo

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

int main()
{
int w, n;
cin >> w >> n;
vector<int> wei(1), val(1);
for(int i = 0; i < n; i++)
{
int a, b;
cin >> a >> b;
wei.push_back(a);
val.push_back(b);
}
vector<vector<int>> dp(n+1, vector<int>(w+1));

for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= w; j++)
{
if(wei[i] > j)
dp[i][j] = dp[i-1][j];
else
dp[i][j] = max(dp[i-1][j-wei[i]]+val[i], dp[i-1][j]);
}
}
cout << dp[n][w] << endl;
}

发表于 2019-08-04 22:46:51 回复(0)

干啥啥不行，吃饭第一名

#include<iostream>
#include<vector>
using namespace std;
struct thing{
    int val;
    int vol;
};
int main(){
    int v,n;
    cin>>v>>n;
    int i,j;
    thing temp;
    vector<thing> t;
    for(i=0;i<n;i++){
        cin>>temp.vol>>temp.val;
        t.push_back(temp);
    }
    int dp[n+1][v+1];
    for(i=0;i<=n;i++)
    for(j=0;j<=v;j++){
        dp[i][0]=0;}
    //先种类再体积
    for(i=1;i<=n;i++){
        for(j=1;j<=v;j++){
            if(t[i].vol>j){
                dp[i][j]=dp[i-1][j];
            }
            else dp[i][j]=max(dp[i-1][j-t[i].vol]+t[i].val,dp[i-1][j]);
        }
    }
    cout<<dp[n][v]<<endl;

}

这个只能过60 哪错了？

发表于 2020-09-15 11:26:24 回复(0)

C/C++

nbgao

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

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

发表于 2019-10-20 19:14:53 回复(1)

牛客107898号

import sys
input = []
for line in sys.stdin:
    input.append(line.strip().split())

volumn = int(input[0][0])
weights = [int(x[0]) for x in input[1:]]
values = [int(x[1]) for x in input[1:]]
num_items = len(weights)

dp = [[0 for _ in range(volumn+1)] for _ in range(num_items)]
for i in range(0, weights[-1]):
    dp[-1][i] = 0
for i in range(weights[-1], volumn+1):
    dp[-1][i] = values[-1]

for i in range(num_items-2, 0, -1):
    for j in range(volumn+1):
        if j < weights[i]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j], dp[i+1][j-weights[i]]+values[i])

if weights[0] > volumn: print(dp[1][volumn])
else: print(max(dp[1][volumn], dp[1][volumn-weights[0]]+values[0]))

90%的python代码。。最后一次不需要循环。

发表于 2019-09-21 16:17:17 回复(0)

Python

牛客117720058号

差1ms。。。

V, n = input().split()
V = int(V)
n = int(n)
W=[]
P=[]
for i in range(n):
    w,p = input().split()
    W.append(int(w))
    P.append(int(p))
    
def knapsack_loop():
    f = [[0 for i in range(V+1)] for j in range(n)]
    for y in range(W[n-1],V+1):
        f[n-1][y] = P[n-1]
    for i in range(n-2,-1,-1):
        for y in range(V+1):
            if y>=W[i]:
                f[i][y] = max(f[i+1][y],f[i+1][y-W[i]]+P[i])
            else:
                f[i][y] = f[i+1][y]
    return f

f=knapsack_loop()
print(f[0][V])

发表于 2023-03-11 23:38:19 回复(0)

C/C++

999JUICE999

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20010;
int dp[N];
int n,v;
int vi[N];
int wi[N];

int main()
{
    scanf("%d%d",&v,&n);
    for(int i = 0;i<n;i++) scanf("%d%d",&vi[i],&wi[i]);
    
    for(int i = 1;i <= n;i++)
        for(int j = v;j >= 1;j--)
            if(vi[i - 1] <= j) dp[j] = max(dp[j],dp[j - vi[i - 1]] + wi[i - 1]);
    
    cout<<dp[v];
    
    return 0;
}

发表于 2022-11-08 23:04:13 回复(0)

卡中卡

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

int main()
{
    int V,N;
    cin>>V>>N;
    vector<int> dp(V+1);
    vector<int> weight(N+1);
    vector<int> value(N+1);
    for(int i=1;i<=N;i++)
    {
        cin>>weight[i]>>value[i];
    }
    for(int i=1;i<=N;i++)
    {
        for(int j=V;j>=weight[i];j--)
        {
            dp[j]=max(dp[j-weight[i]]+value[i], dp[j]);
        }
    }
    cout<<dp[V];
    return 0;
}

一维dp

发表于 2022-06-07 11:52:41 回复(0)

Black-K

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

int main(){
    int n,m;//n个数 m：包体积
    cin>>m>>n;
    if(n==0 || m==0){
        cout<<0;
        return 0;
    }
    vector<int> V;//价值
    vector<int> A;//体积
    int x, y;
	for (int i = 0; i < n; ++i) {
		cin >> x >> y;
		A.push_back(x);
		V.push_back(y);
	}
    vector<int> ans(m+1,0);
     for(int i=1;i<=n;++i){
        for(int j=m;j>0;--j){
            if(j>=A[i-1])
            ans[j]=max(ans[j],V[i-1]+ans[j-A[i-1]]);
        }
    }
    /*
    vector<vector<int>> ans(n+1,vector<int>(m+1,0));
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(A[i-1]>j){
                ans[i][j]=ans[i-1][j];
            }else{
                ans[i][j]=max(ans[i-1][j],V[i-1]+ans[i-1][j-A[i-1]]);
            }
        }
    }
    */
    cout<<ans[m];
    
    return 0;
}

发表于 2022-02-18 17:14:10 回复(0)

牛客335794154号

#include<stdio.h>
#define max(a,b) (a>b?a:b)

int main( void )
{
int n, v;
int vo[1001] = {0},va[1001] = {0},dp[20001]={0};
while(scanf("%d %d",&v,&n) != EOF)//输入背包容积和物品数量
{
for(int i = 0; i < n; i++)
{
scanf("%d %d",&vo[i],&va[i]);//输入每件物品体积和价值
}
}
for(int i = 0; i < n; i++)//计算最大价值
{
for(int j = v; j >= vo[i]; j--)
{
dp[j] = max(dp[j-vo[i]]+va[i], dp[j]);
}
}
printf("%d",dp[v]);
return 0;

}

发表于 2021-09-08 17:01:13 回复(0)

Python

牛客45854653号

def knapsack(V , n , vw ):
    dp=[[0]*(V+1) for _ in range(n+1)]
    for i in range(1,n+1):
        vi=vw[i-1][0]
        wi=vw[i-1][1]
        for j in range(1,V+1):
            if vi>j:
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-vi]+wi)
    return dp[-1][-1]
V , n =map(int,input().split())
vw=[]
for _ in range(n):
    v,w=map(int,input().split())
    vw.append([v,w])
print(knapsack(V , n , vw ))

发表于 2021-09-02 11:31:15 回复(1)

Java

D_Y_Y

import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int V = scanner.nextInt();
int N = scanner.nextInt();
int[][] bag = new int[N][2];
for(int i = 0; i < N; i++) {
bag[i][0] = scanner.nextInt();
bag[i][1] = scanner.nextInt();
}
int[] dp = new int[V+1];//背包容量为v最大能存放多少价值的物品dp[v]
for(int i = 0; i < N; i++) {
for(int j = V; j >= bag[i][0]; j--) {
dp[j] = Math.max(dp[j], dp[j-bag[i][0]] + bag[i][1]); //比较，放不放物品i的价值
}
}
System.out.println(dp[V]);
}
}

发表于 2021-08-17 17:29:00 回复(0)

soyyazzz

22ms, 616KB

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // Read inputs
    unsigned W, N;  // Weight Limit, Number of items
    cin >> W >> N;
    vector<int> weight;
    vector<int> val;
    for (unsigned i = 0; i < N; i++) {
        int x1, x2;
        cin >> x1 >> x2;
        weight.push_back(x1);
        val.push_back(x2);
    }
    
    // Core code
    vector<int> dp(W + 1, 0);
    for (unsigned i = 0; i < N; i++) {
        for (unsigned w = W; w >= weight[i]; w--) {
            dp[w] = max(dp[w], dp[w - weight[i]] + val[i]);
        }
    }
    
    // Output
    cout << dp[W];
    
    return 0;
}

发表于 2021-07-05 20:04:57 回复(0)

<云昊>

package main

import "fmt"

func main() {
	var v int
	var n int
	fmt.Scan(&v,&n)
	volumes := make([]int,n)
	values := make([]int,n)
	var volume int
	var value int
	for i:=0;i<n;i++{
		fmt.Scan(&volume,&value)
		volumes[i] = volume
		values[i] = value
	}
	maxValue := knapsack(v,n,volumes,values)
	fmt.Println(maxValue)
}
func knapsack(v,n int,volumes,values []int) int {
	dp := make([][]int,n+1)
	for i:=0;i<=n;i++{
		dp[i] = make([]int,v+1)
	}
	for i:=1;i<=n;i++{
		volume := volumes[i-1]
		value := values[i-1]
		for j:=1;j<=v;j++{
			if j>=volume {
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-volume]+value)
			}else {
				dp[i][j]=dp[i-1][j]
			}
		}
	}
	return dp[n][v]
}
func max(a,b int) int {
	if a>b {
		return a
	}
	return b
}

Go语言这么不受待见？居然没有专门的插入格式

发表于 2020-09-25 00:02:16 回复(1)

all_might


import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int V = in.nextInt();
        int n = in.nextInt();
        int[][] pack = new int [n + 1][2];
        for(int i = 1; i <= n; i++){
            pack[i][0] = in.nextInt();
            pack[i][1] = in.nextInt();
        }
        int[][] dp = new int[n + 1][V + 1];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= V; j++){
                // 此时物品体积大于背包容积，故不能放进背包，因此最大价值为
                if(pack[i][0] > j){
                    dp[i][j] = dp[i - 1][j];
                }
                else{
                    // 此时空间够大，可以选择物品i和不选择物品i
                                        // 不选择，则为dp[i - 1][j]，即为前i-1个物品在空间为j时的最优解

                                        // 选择时，则为前i - 1个物品，在空间为j - 物品i所占空间的最优解
                    dp[i][j] = Math.max(dp[i - 1][j], (dp[i - 1][j - pack[i][0]] + pack[i][1]));
                }
            }
        }
                // 输出整个dp数组
        for(int[] i : dp){
            for(int j : i){
                System.out.print(j + " ");
            }
            System.out.println();
        }
        System.out.println(dp[n][V]);
    }
}

发表于 2020-09-11 11:01:11 回复(0)

bosinica

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
int ans = INT32_MIN;

size_t contain, n;
std::cin >> contain >> n;
std::vector<int> weights(n + 1);
std::vector<int> values(n + 1);

for (int count = 1; count <= n; ++count) {
int w, v;
std::cin >> w >> v;
weights[count] = w;
values[count] = v;
}

std::vector<std::vector<int>> dp(contain + 1, std::vector<int>(n + 1));

for (size_t i = 0; i < dp.size(); ++i) {
dp[i][0] = 0;
}

for (size_t i = 0; i < dp[0].size(); ++i) {
dp[0][i] = 0;
}

for (int i = 1; i < dp.size(); ++i) {
for (int j = 1; j < dp[0].size(); ++j) {
// 要装第j个
int opt1 = INT32_MIN;
if (i - weights[j] >= 0) {
opt1 = dp[i - weights[j]][j - 1] + values[j];
}

// 不装第j个
int opt2 = dp[i][j - 1];

dp[i][j] = std::max(opt1, opt2);
ans = std::max(ans, dp[i][j]);
}
}

std::cout << ans << std::endl;

return 0;
}

发表于 2020-08-24 16:57:40 回复(0)

陈晨201809010830229

import java.util.Scanner; public class Main{ public static void main(String[] args){
        Scanner sc = new Scanner(System.in); int V = sc.nextInt(); int n = sc.nextInt();
        Thing[] things = new Thing[n]; for(int i=0;i<n;i++){ int v; int w;
            v=sc.nextInt();
            w=sc.nextInt();
            Thing thing = new Thing(v,w);
            things[i]=thing;
        } int[] dp = new int[V+1]; for(int i=0;i<n;i++){ for(int j=V;j>0;j--){ int max = dp[j]; if(j-things[i].vo>=0 && max<things[i].we+dp[j-things[i].vo]){
                    max = things[i].we+dp[j-things[i].vo];
                } if(max>dp[j]){
                    dp[j]=max;
                }
            }
        }
        System.out.println(dp[V]);
    }
} class Thing{ int vo; int we; public Thing(int vo,int we){ this.vo = vo; this.we = we;
    }
}

发表于 2020-05-28 23:25:29 回复(0)

C/C++

RichardLee0

#include<iostream>
#include<math.h>
using namespace std;
int main(){
    int n,c;
    cin>>c>>n;
    int w[n],v[n],dp[c+1];
    for(int i=0;i<n;i++)
        cin>>w[i]>>v[i];
    for(int j=0;j<=c;j++)
        if(w[0]<=j) dp[j]=v[0];
        else dp[j]=0;
    for(int i=1;i<n;i++)
        for(int j=c;j>=w[i];j--){
            dp[j]=max(dp[j], v[i]+dp[j-w[i]]);
        }
    cout<<dp[c]<<endl;
    return 0;
}

发表于 2020-02-02 22:18:21 回复(0)

~似曾相识燕归来

C++实现，时间复杂度O(NV)，空间复杂度O(V)。

#include<bits/stdc++.h>

using namespace std;

int main() {
    int V, N;

    cin >> V >> N;

    vector<int> dp(V + 1, 0);

    vector<int> vVct, wVct;
    vVct.reserve(N + 1);
    wVct.reserve(N + 1);

    int tmpV, tmpW;
    for (int i = 0; i < N; ++i) {
        cin >> tmpV >> tmpW;
        vVct.push_back(tmpV);
        wVct.push_back(tmpW);
    }

    for (int i = 0; i < N; ++i) {
        for (int j = V; j >= vVct[i]; --j) {
            dp[j] = max(dp[j], dp[j - vVct[i]] + wVct[i]);
        }
    }

    cout << dp[V] << endl;

    return 0;
}

发表于 2019-10-14 20:55:59 回复(0)

ICDD

#AC代码

#include<iostream>

using namespace std;
int Max(int a,int b){
return a>b?a:b;
}
int main(){
int v,n,x,y;
int dp[20005]={0};
cin>>v>>n;
while(n--){
cin>>x>>y; //V value
for(int i=v;i>=x;i--){
dp[i]=Max(dp[i],dp[i-x]+y);
}
}
cout<<dp[v]<<endl;
}

发表于 2019-09-11 10:47:33 回复(0)

boney

我看分享答案的都没有用python的，可能是因为用python貌似都会超时，ac为90%，我就来第一个分享python的做法吧，

代码应该没问题，这个用二维数组保存结果的方法，供参考：

input1 = list(map(int,input().strip().split()))
KG = input1[0]
nums = input1[1]
weights = []
values = []
for i in range(nums):
    input_wuti = list(map(int,input().strip().split()))
    weights.append(input_wuti[0])
    values.append(input_wuti[1])
V = [[0]*(KG+1) for j in range(len(weights)+1)]  # 初始化一个二维数组
for k in range(1,len(weights)+1):  # 这里k从1开始，因为当提供的物品为0个时，总价值必然为0，也就是V[0][h]=0
    for h in range(1,KG+1):  # 这里h从1开始，因为当背包体积为0时，总价值必然为0，也就是V[k][0]=0
        if h-weights[k-1]<0:
            V[k][h] = V[k-1][h]
        else:
            V[k][h]=max(V[k-1][h], V[k-1][h-weights[k-1]]+values[k-1])
print(V[len(weights)][KG])

这个是用一维数组的情况，通过率也是90%，也是超时的问题，代码思路应该没问题，如下：

task={}
n,m = map(int,input().strip().split())  # n为总体积，m为物品个数
a,b = [], []  # a为体积，b为价值
for i in range(m):
    a_, b_ = map(int,input().strip().split())
    a.append(a_)
    b.append(b_)
max_value = [0]*(n+1)  # max_value[j]表示总体积为j时的最大价值，max_value[0]必然为0
temp = [k for k in range(1,n+1)][::-1]  # 逆序
for i in range(m):
    for j in temp:  # 注意这里要反向枚举，所以前面做了逆序
        if j>=a[i]:  # 当前剩余体积比遇到的物品的体积大，就把物品的价值加上，再与不把物品加上去的情况进行比较
            max_value[j] = max(max_value[j],max_value[j-a[i]]+b[i])
print(max_value[n])

编辑于 2019-09-10 14:33:57 回复(2)