有N件物品和一个容量为V的背包。第i件物品的价值是C[i]，重量是W[i]。求解将哪些物品装入背包可使价值总和最大。
[编程题]背包问题
动态规划，Python版
import sys N,V = map(int,sys.stdin.readline().split()) values = [0]*(N+1) weights = [0]*(N+1) i = 1 for line in sys.stdin.readlines(): values[i],weights[i] = map(int,line.split()) i+=1 dp = [[0]*(V+1) for _ in range(N+1)] #dp[i][j] 面对第i个物品，背包容量为j时的价值最大值 for i in range(1,N+1): for j in range(1,V+1): if j>= weights[i]: dp[i][j] = max(dp[i-1][j],dp[i-1][j-weights[i]]+values[i]) else: dp[i][j] = dp[i-1][j] #不要这个东西，价值和i-1一样，容量不变 print(dp[-1][-1])
发表于 2020-05-30 20:46:48
回复(1)
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
int N, V;
cin >> N>>V;
vector<int> C(N + 1, 0);
vector<int> W(C);
for (int i = 1; i<=N; i++)
cin >> C[i] >> W[i];
vector<vector<int>> dp(N + 1, vector<int>(V + 1,0));
for(int i=1;i<=N;i++)//i是物品号，从1开始 N是背包容量
for (int j = 1; j <= V; j++)
{
if (j < W[i])//装不下
dp[i][j] = dp[i - 1][j];
else
{
dp[i][j] = max(dp[i - 1][j], (dp[i - 1][j - W[i]] + C[i]));
}
}
cout << dp[N][V];
}
发表于 2021-03-24 17:33:30
回复(0)
n,v=map(int,input().split()) c=[0 for i in range(n)] w=[0 for i in range(n)] for i in range(n): c[i],w[i]=map(int,input().split()) def package (n,v,c,w): d=[[0 for i in range(v+1)] for j in range(n+1)] for i in range(1,n+1): for j in range(1,v+1): if j>=w[i-1]: d[i][j]=max(d[i-1][j],d[i-1][j-w[i-1]]+c[i-1]) else: d[i][j]=d[i-1][j] #return max(map(max,d)) return d[-1][-1] print(package(n,v,c,w))
发表于 2021-03-20 12:57:38
回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int N,V=0;
while(cin>>N>>V){
vector<int> c(N);
vector<int> w(N);
for(int i=0;i<N;++i){
cin>>c[i]>>w[i];
}
vector<int> dp(V+1);
for(int i=0;i<N;++i){
for(int j=V;j>=w[i];--j){
dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
}
}
cout<<dp[V];
}
return 0;
}
编辑于 2020-08-05 21:56:35
回复(0)
动态规划：
子问题：背包容量为1~V逐次递增时的最优方案
子子问题：遍历物品序号，装第一个物品到装最后一个物品时在不同的背包容量时的最优方案
#include<iostream>
using namespace std;
#include<vector>
int main()
{
int N,V;
while(cin >> N >> V)
{
vector<int> value(N);//存储每个物品的价值
vector<int> capacity(N);//存储每个物品的容量
for(int i = 0; i < N; ++i)
{
cin >> value[i] >> capacity[i];
}
vector<vector<int>> dp(N+1,vector<int>(V+1,0));
//有N+1行，但是从1开始遍历，所以每行表示每个物品
//有V+1列，但是从1开始遍历，所以每列表示从1开始到最大容量 的 各种情况下 的 物品最大价值存储
for(int i = 1; i < N+1; ++i)
{
for(int j = 1; j < V+1; ++j)
{
if(capacity[i-1] > j)//如果不下，那就等于上次的最优存储
{//这里的capacity[i-1]是因为这里的i从1开始
dp[i][j] = dp[i-1][j];
}
else//如果能放下，有两种情况：1、放 2、不放
//放和不放取决于放了之后是否是最优的，于是创建一个临时变量。
{//dp[i-1][j-capacity[i-1]]：i-1：上面一行，j-capacity[i-1]：装了i-1这个物品之后还剩的容量。所以整体就是：当前的tmp_best == 装了i-1物品的价值 + 装了这个物品后剩余的容量还可以装的最优的方案
int tmp_best = value[i-1] + dp[i-1][j-capacity[i-1]];
dp[i][j] = max(tmp_best,dp[i-1][j]);
}
}
}
//返回最后一个元素就是最优的方案
cout << dp[N][V] << endl;
}
return 0;
}
发表于 2020-02-01 17:22:11
回复(1)
#include<iostream>
usingnamespacestd;
intmain() {
intN, V;
cin >> N;//N件物品
cin >> V;//背包最大容量为V
int* val = (int*)malloc(sizeof(int) * N);
int* tiji = (int*)malloc(sizeof(int) * N);
int* dp = (int*)malloc(sizeof(int) * (V + 1)); //dp[j]表示体积j下可装的物品组成的最大总价值
//开辟V+1的空间是因为假设背包体积为12，那么就需要开辟0~12，即十三个空间大小
for(inti = 0; i < N; i++) {
cin >> val[i];//第i件物品的价值
cin >> tiji[i];//第i件物品所占的空间
}
for(inti = 0; i < N; i++) {
for(intj = V; j >= tiji[i]; j--) {
dp[j] = max(dp[j - 1], dp[j - tiji[i]] + val[i]);
}
}
cout << dp[V];//dp[V]表示这个背包能装下的物品组合中，价值最大化的组合所得到的价值
return0;
}
发表于 2024-01-08 11:54:04
回复(0)
python暴力递归解法：
def bagvalue(c:list,w:list,v:int): if len(c)!=len(w)&nbs***bsp;len(c) == 0&nbs***bsp;len(w) == 0: return 0 return process(c,w,0,v) def process(c:list,w:list,index:int,v:int): if v < 0: return -1 if index == len(c): return 0 p1 = process(c,w,index+1,v) p2=0 nextindex = process(c,w,index+1,v - w[index]) if nextindex != -1: p2 = c[index] + nextindex return max(p1,p2) n,v = map(int,input().split()) c,w = [],[] for i in range(n): c1,w1 = map(int,input().split()) c.append(c1) w.append(w1) print(bagvalue(c,w,v))python动态规划解法：
def dp(c:list,w:list,v:int): n = len(c) #***重要！！！python数组定义方式用for循环 dp = [[0 for _ in range(v+1)]for _ in range(n+1)] for index in range(n-1,-1,-1): for rest in range(v+1): p1 = dp[index+1][rest] nextindex = -1 if rest-w[index] <0 else dp[index+1][rest-w[index]] p2 = 0 if nextindex != -1: p2 = c[index] + nextindex dp[index][rest] = max(p1,p2) return dp[0][v] n,v = map(int,input().split()) c,w = [],[] for i in range(n): c1,w1 = map(int,input().split()) c.append(c1) w.append(w1) print(dp(c,w,v))
发表于 2022-08-15 22:36:38
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// String first = in.nextLine();
// String[] firstArray = first.split(" ");
// int n = Integer.parseInt(firstArray[0]);
// int c = Integer.parseInt(firstArray[1]);
int n = in.nextInt();
int v = in.nextInt();
int[] values = new int[n+1];
int[] weights = new int[n+1];
// 注意 hasNext 和 hasNextLine 的区别
for (int i = 0; i < n; i++) { // 注意 while 处理多个 case
values[i] = in.nextInt();
weights[i] = in.nextInt();
}
// int[][] result = new int[n][v];
int result[][] = new int[n + 1][v + 1];
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < v + 1; j++) {
//使用动态转移方程对二维数组赋值
if (j < weights[i]) {
result[i][j] = result[i - 1][j];
} else {
result[i][j] = Math.max(result[i - 1][j],
result[i - 1][j - weights[i]] + values[i]);
}
}
}
System.out.println(result[n][v]);
// if (i == 0 || j == 0 ) {
// dp[i][j] = 0;
// continue;
// }
// if (bbc[i] < j) {
// dp[i][j] = dp[i-1][j];
// } else {
// dp[i][j] = Math.max(dp[i-1][j], dp[i-1][v] + bbw[i]);
// }
// }
// }
// System.out.println(dp[n][v]);
}
}
发表于 2024-01-08 22:22:19
回复(0)
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // n件物品
int v = sc.nextInt(); // 容量v
int[] c = new int[n]; // 单件价值
int[] w = new int[n]; // 单间重量
for (int i = 0; i < n; i++) {
c[i] = sc.nextInt();
w[i] = sc.nextInt();
}
//
int[][] dp = new int[n][v];
// 初始化第一行
for (int i = 0; i < v; i++) {
if (i >= w[0]) {
dp[0][i] = w[0];
} else {
dp[0][i] = 0;
}
}
// 遍历物品
for (int i = 1; i < n; i++) {
// 遍历容量
for (int j = 0; j < v; j++) {
if (j < w[i]) {
// 空间不足
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + c[i]);
}
}
}
System.out.println(dp[n-1][v-1]);
sc.close();
}
编辑于 2023-12-27 23:57:49
回复(0)
python递归啰嗦版【既能保存下最大价值，同时还能保存下是哪些物品组合出当前的最大价值，因此，比较啰嗦，毕竟题目没有要求输出组合】
import sys
count=0
param={}
elements=[]
for line in sys.stdin:
a = line.split()
if count==0:
param["N"]=int(a[0])
param["V"]=int(a[1])
pass
elif count<=param["N"]:
single={}
single["C"]=int(a[0])
single["W"]=int(a[1])
elements.append(single)
pass
else:
break
count += 1
# 最终要查询保存的表 共计N+1 行 下标从1开始
F=[[0 for j in range(param["V"]+1)] for i in range(param["N"]+1)]
def getMaxOne(v:int,initList:list[dict],already:list[int])->list:
# 获取单件物品最大价值
maxValue = 0
maxIndex = -1
for i in range(len(initList)):
if i in already:
continue
item = initList[i]
if item["W"]<=v and item["C"]>maxValue:
maxValue = item["C"]
maxIndex = i
pass
pass
# F[1][V]
if maxValue>0:
F[1][v]=maxValue
return [maxIndex]
def calculateF(i:int,v:int,initList:list[dict],alreadyInput:list[int])->list:
# 计算 i 个物品 V 的容量条件下的最大价值
if i==1:
return getMaxOne(v,initList,alreadyInput)
else:
# F[i-1][V]
already1 = calculateF(i-1,v,initList,alreadyInput)
maxValue = F[i-1][v]
alreadyOut = already1
# F[i-1, v − Wi] + Ci
for iterNum in range(len(initList)):
if iterNum in alreadyInput:
continue
item = initList[iterNum]
C = item["C"]
W = item["W"]
if (v-W)<=0:
continue
alreadyTemp = [iterNum]
alreadyTemp.extend(alreadyInput)
already2 = calculateF(i-1,v-W,initList,alreadyTemp)
if -1 in already2:
continue
twoPlus = F[i-1][v-W]+C
already2.append(iterNum)
if twoPlus>maxValue:
maxValue = twoPlus
alreadyOut = already2
pass
F[i][v]=maxValue
return alreadyOut
pass
already = calculateF(param["N"],param["V"],elements,[])
print(F[-1][-1]) 最后的already就是最大价值使用的物品的下标
编辑于 2023-06-09 14:17:39
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
//输入物品件数
int n = in.nextInt();
//输入背包容量
int v = in.nextInt();
//存放物品价值数组
int values[] = new int[n + 1];
//存放物品重量数组
int weights[] = new int[n + 1];
//初始化结果的二维数组
int result[][] = new int[n + 1][v + 1];
//向价值数组和重量数组存数
for(int i = 1;i < n + 1;i++){
values[i] = in.nextInt();
weights[i] = in.nextInt();
}
//使用动态转移方程对二维数组赋值
for(int i = 1;i < n + 1;i++){
for(int j = 1;j < v + 1;j++){
if(j < weights[i]){
result[i][j] = result[i - 1][j];
}else{
result[i][j] = Math.max(result[i - 1][j],result[i - 1][j - weights[i]] + values[i]);
}
}
}
System.out.println(result[n][v]);
}
}
发表于 2023-05-13 10:29:01
回复(0)
(30ms) 动态规划 + 压缩状态 + 遍历优化
时间: O(容量 * 物品数)
空间: O(容量)
import sys # n: 物品数量 cap: 背包容量 n, cap = list(map(int, input().split())) # values: 物品价值 weights: 物品重量 values, weights = [], [] for _ in range(n): v, c = list(map(int, input().split())) values.append(v); weights.append(c) # 初始化 dp dp = [values[0] if c >= weights[0] else 0 for c in range(cap)] # 迭代 dp for i in range(n): for c in range(cap-1,weights[i]-1, -1): dp[c] = max(dp[c], dp[c - weights[i]] + values[i]) print(dp[-1])
编辑于 2023-03-24 17:10:57
回复(0)
#include<iostream>
#include<algorithm>
using namespace std;
int V[10001]; //体积 - 最大价值数组
int main()
{
int N = 0;//物品数量
int backpack_size = 0;
cin >> N >> backpack_size;
while(N)
{
int w = 0; //质量
int v = 0; //价值
cin >> v >> w;
for(int i = backpack_size; i >= w; --i)
{
if(w < backpack_size)
V[i] = max(V[i] , V[i - w] + v);
}
--N;
}
cout << V[backpack_size];
return 0;
}
发表于 2023-03-24 00:28:37
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(), V = sc.nextInt();
int[] wei = new int[N];
int[] val = new int[N];
for(int i = 0; i < N; i++){
val[i] = sc.nextInt();
wei[i] = sc.nextInt();
}
int[] dp = new int[V + 1];
for(int i = 0; i < N; i++){
for(int j = V; j > 0; j--){
if(j >= wei[i])
dp[j] = Math.max(dp[j], dp[j - wei[i]] + val[i]);
}
}
System.out.print(dp[V]);
}
}
发表于 2022-10-23 18:01:14
回复(0)
// JS DP动态规划二维数组解决法：
let [count, volume] = readline().split(" ").map(item => parseInt(item));
let valueAndWeight;
let goodsList = [];
while (valueAndWeight = readline()) {
let list = valueAndWeight.split(" ");
goodsList.push([parseInt(list[0]), parseInt(list[1])]);
}
// 按重量排序，第二列输入为重量
goodsList.sort((a, b) => a[1] - b[1]);
// 得出 C、W 数组，需要填充第一个为0，对应容量为0 的情况
let cList = [0], wList = [0];
for (let k = 0; k < goodsList.length; k++) {
cList.push(goodsList[k][0]);
wList.push(goodsList[k][1]);
}
// 计算得出dp(dynamic programming)数组
let dpList = [];
for (let i = 0; i < goodsList.length + 1; i++) {
if (dpList[i] === undefined) {
dpList[i] = [];
}
for (let j = 0; j < volume; j++) {
dpList[i][j] = 0;
if (i === 0 || j === 0) { // 填充第0行及第零列，避免动态转换公式 i - 1 和 j - 1 的情况
dpList[i][j] = 0;
} else if (j < wList[i]) { // 拿不了当前物品的情况
dpList[i][j] = dpList[i - 1][j];
} else if (j >= wList[i]) { // 拿的了当前物品的情况
let gotJValue = cList[i] + dpList[i - 1][j - wList[i]]; // 拿当前物品得到的最大价值 = 当前物品价值 + 前面物品在剩余重量下的最大价值：value = dpList[i - 1][j - w[i]] + c[i]
let noJValue = dpList[i - 1][j]; // 不拿当前物品的最大价值 = 前面物品在当前重量下的最大价值：value = dpList[i - 1][j]
dpList[i][j] = Math.max(gotJValue, noJValue);
}
}
}
console.log(dpList[dpList.length - 1][dpList[dpList.length - 1].length - 1]);
/**
* 一维数组解法：
* 空间优化为一维数组，滚动式数组，实际就是根据后无效原则，进行滚动式更新数组，
* 原因是每轮滚动，数组实际只和上一轮数组有关，和再之前的 i - 2 序列的数组无关
*/
let [count, volume] = readline().split(" ").map(item => parseInt(item));
let valueAndWeight;
let goodsList = [];
while (valueAndWeight = readline()) {
let list = valueAndWeight.split(" ");
goodsList.push([parseInt(list[0]), parseInt(list[1])]);
}
// 按重量排序，第二列输入为重量
// goodsList.sort((a, b) => a[1] - b[1]);
// 得出 C、W 数组，需要填充第一个为0，对应容量为0 的情况
let cList = [0], wList = [0];
for (let k = 0; k < goodsList.length; k++) {
cList.push(goodsList[k][0]);
wList.push(goodsList[k][1]);
}
// 计算得出dp(dynamic programming)数组
let dpList = [];
for (let i = 0; i < goodsList.length + 1; i++) {
for (let j = volume; j >= 0; j--) { // *****重点：需要逆序递推，避免前序元素被早替换导致
dpList[j] = dpList[j] === undefined ? 0 : dpList[j];
if (j >= wList[i]) { // 拿的了当前物品的情况
let gotJValue = cList[i] + dpList[j - wList[i]]; // 拿当前物品得到的最大价值 = 当前物品价值 + 前面物品在剩余重量下的最大价值：value = dpList[j - w[i]] + c[i]
let noJValue = dpList[j]; // 不拿当前物品的最大价值 = 前面物品在当前重量下的最大价值：value = dpList[j]
dpList[j] = Math.max(gotJValue, noJValue);
}
}
}
console.log(dpList[dpList.length - 1]);
编辑于 2022-09-12 11:16:09
回复(0)
# python版递归解法 n, v = map(int, input().split()) C , W = [], [] for i in range(n): c, w = map(int, input().split()) C.append(c) W.append(w) total = 0 maxval = 0 def dfs(v, C, left): global maxval global total if left==[]&nbs***bsp;min(left)>v: if maxval>total: total = maxval return for i in range(len(left)): if left[i]<=v: v-=left[i] maxval+=C[i] temp_left = left[:] temp_C = C[:] temp_left.pop(i) temp_C.pop(i) dfs(v, temp_C, temp_left) maxval-=C[i] v+=left[i] dfs(v, C[:], W[:]) print(total)
发表于 2022-08-12 15:16:05
回复(0)
//一维数组01背包问题
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int N, V;
while(cin >> N >> V)
{
vector<int> dp(V + 1, 0);
vector<int> C(N + 1, 0);//价值
vector<int> W(N + 1, 0);//重量
for(int i = 1; i <= N; i++)
cin >> C[i] >> W[i];
for(int i = 1; i <= N; i++)
{
//此处已经进行了优化，背包重量小于当前物品的重量，则空包都放不进去，直接跳过
for(int j = V; j >= W[i]; j--)
{
dp[j] = dp[j] > dp[j - W[i]] + C[i] ? dp[j] : dp[j - W[i]] + C[i];
}
}
cout << dp[V] << endl;
}
return 0;
}
发表于 2021-11-14 22:33:34
回复(0)
前面的算法都是类似的，动态规划，我的理解：
求N个物品，容量V的最优解，这个直接搞不定。那么：只有一个物品呢，那必须可以啊。
搞定了一个物品，容量为1,2...N的各个容量的最优解为{ dp[1]，dp[2]，... dp[n] }；
那么再添加一个物品，求2个物品，容量为V的最优解，能不能搞定呢？答案是可以的：
2个物品，容量为V的最优解，就两种情况：
a）不放入第二个物品，那么最优解就是：1个物品时的最优解；即：
dp[n]；
b）放入第二个物品，那么最优解就是“放入后，剩余容量，的最优解”。即：
dp[ V - W(2) ]
依次类推，每次加一个数，我们就知道N个数时的最优解了；
发表于 2021-11-13 14:22:20
回复(0)
核心在于，你怎么去定义这个状态。以容量为核心状态变化行不通。
以个数变化可以
N,V = map(int,input().split()) pro = [] dp = [] for i in range(N): pro.append(list(map(int,input().split()))) for i in range(N+1): dp.append([0 for i in range(V+1)]) for i in range(1,N+1): for j in range(V+1): if pro[i-1][1] > j : continue dp[i][j] = max(dp[i-1][j - pro[i-1][1]] + pro[i-1][0],dp[i-1][j]) print(dp[N][V])
发表于 2021-10-09 15:23:28
回复(0)
01背包问题，在自己编译器上调试运行用例都通过了，在牛客上运行报错，说是溢出
#include <bits/stdc++.h>
using namespace std;
//01背包问题，最值问题
int main(){
int n, v;
vector<vector<int> > goods(n, vector<int>(2, 0));//value，weight
cin >> n >> v;
for (int i = 0; i < n; i++) {
cin >> goods[i][0] >> goods[i][1];
}
vector<int> dp(v + 1, 0);
for(int i = 1; i < goods.size(); i++) {
for (int j = v; j >= goods[i][1]; j--) {
dp[j] = max(dp[j], dp[j - goods[i][1]] + goods[i][0]);
}
}
cout << dp[v];
return 0;
}
发表于 2021-08-25 14:54:10
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
