你有一个背包，最多能容纳的体积是V。
现在有n种物品，每种物品有任意多个，第i种物品的体积为
,价值为
。
（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？
[编程题]【模板】完全背包
- 热度指数：13162 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
输入描述:
第一行两个整数n和V，表示物品个数和背包体积。接下来n行，每行两个数
输出描述:
输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。
示例1
输入
2 6 5 10 3 1
输出
10 2
示例2
输入
3 8 3 10 9 1 10 1
输出
20 0
说明
无法恰好装满背包。
示例3
输入
6 13 13 189 17 360 19 870 14 184 6 298 16 242
输出
596 189
说明
可以装5号物品2个，达到最大价值298*2=596，若要求恰好装满，只能装1个1号物品，价值为189.
参考兑换零钱的一维数组解法，把背包容量看做零钱中的target，外层循环容量，内层循环物品（python3）。
import sys
def solution(n,V,v,m):
dp1 = [0 for _ in range(V+1)]
dp2 = [float("-inf") for _ in range(V+1)]
dp2[0] = 0
for i in range(V+1):
for j in range(n):
if i<v[j]:break
#if dp2[i-v[j]] != float('-inf'):# 可以省略
dp1[i] = max(dp1[i],dp1[i-v[j]]+w[j])
dp2[i] = max(dp2[i],dp2[i-v[j]]+w[j])
#print(dp1)
#print(dp2)
if dp2[-1] == float("-inf"):
dp2[-1] = 0
return dp1[-1],dp2[-1]
if __name__ == "__main__":
n,V = map(int, input().split())
v = [0 for _ in range(n)]
w = [0 for _ in range(n)]
p = [0 for _ in range(n)]
for i in range(n):
p[i] = list(map(int,input().split()))
p = sorted(p, key=lambda x:(x[0],x[1]))
v,w =zip(*p)
#print(v,w)
res1,res2 = solution(n,V,v,w)
print(res1)
print(res2)
发表于 2022-05-09 11:00:38
回复(0)
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
int f[N];
int main()
{
int n, m;
cin >> n >> m;
memset(f, -0x3f, sizeof(f));
f[0] = 0;
for(int i = 1; i <= n; i++)
{
int v, w;
cin >> v >> w;
for(int j = v; j <= m; j++)
f[j] = max(f[j], f[j - v] + w);
}
int ret = 0;
for(int i = 1; i <= m; i++)
ret = max(ret, f[i]);
if(f[m] < 0)
f[m] = 0;
cout << ret << endl;
cout << f[m] << endl;
return 0;
}
发表于 2022-11-27 19:55:31
回复(0)
#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=weight[i];j<=V;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=weight[i];j<=V;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:32:06
回复(0)
普通解法
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
static int capacity;//背包容量
static int count;//物品个数
static int [] v;//物品体积
static int [] w;//物品价值
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
count = in.nextInt();
capacity = in.nextInt();
v = new int[count+1];
w = new int[count+1];
//读取物品体积和价值，从1开始
for(int i = 1;i <= count;i++){
v[i] = in.nextInt();
w[i] = in.nextInt();
}
//背包不装满情况
int ret1 = notFilled();
//背包装满情况
int ret2 = filled();
//打印结果
System.out.println(ret1);
System.out.println(ret2);
}
private static int notFilled(){
//初始化dp表，dp[i][j]表示从前i个物品中的所有选法中体积不超过j的最大价值
int [][] dp = new int[count+1][capacity+1];
//我们无需初始化，因为对于边界情况，比如第一列，我们填表的时候会进行特殊判断
//同时对于第一行，没有选择物品最大价值肯定是0嘛
//——————————————状态转移方程推导———————————————————
//如果我们不选当前i物品，那我们直接dp[i-1][j]
//如果我们选择一个i物品，则为dp[i-1][j-v[i]]+w[i]
//如果我们选择两个i物品，则为dp[i-1][j-2v[i]]+2w[i]
//.........
//如果我们选择k个i物品（不超过背包容量），则为dp[i-1][j-kv[i]]+kw[i]
//—————————————————————————————————————————————————
//如果我们进行等价替换，把dp[i][j]中j-->j-v[i]，则方程变为
//dp[i-1][j-v[i]] dp[i-1][j-2v[i]]+w[i] ......... dp[i-1][j-kv[i]]+(k-1)w[i]
//发现没有，我们如果进行等价替换，dp[i][j-v[i]]就包括了dp[i][j]从dp[i][j-v[i]]+w[i]开始后面的值
//并且只相差一个w[i]，我们直接加上就好了
//因此我们最终的状态转移方程是Math.max(dp[i-1][j],dp[i][j-v[i]]+w[i])
for(int i = 1;i <= count;i++){
for(int j = 0;j <= capacity;j++){
dp[i][j] = dp[i-1][j];
//判断背包剩余空间是否符合要求
if(j >= v[i]){
dp[i][j] = Math.max(dp[i][j],dp[i][j-v[i]]+w[i]);
}
}
}
return dp[count][capacity];
}
private static int filled(){
int [][] dp = new int[count+1][capacity+1];
//初始化，对于第一列我们不用管，因为我们填表会进行判断
//但是对于第一行，第一个位置是0，因为我们没有选物品体积为0就是0
//但是从下一个开始，我们为了区分究竟是不存在状态还是初始化状态
//-1表示这个状态不存在，0就表示默认
for(int i = 1;i <= capacity;i++){
dp[0][i] = -1;
}
for(int i = 1;i <= count;i++){
for(int j = 0;j <= capacity;j++){
dp[i][j] = dp[i-1][j];
if(j >= v[i] && dp[i][j-v[i]] != -1){
dp[i][j] = Math.max(dp[i][j],dp[i][j-v[i]]+w[i]);
}
}
}
return dp[count][capacity] == -1 ? 0 : dp[count][capacity];
}
} 我们可以做空间优化，常数级别的时间复杂度优化
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
static int capacity;//背包容量
static int count;//物品个数
static int [] v;//物品体积
static int [] w;//物品价值
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
count = in.nextInt();
capacity = in.nextInt();
v = new int[count+1];
w = new int[count+1];
//读取物品体积和价值，从1开始
for(int i = 1;i <= count;i++){
v[i] = in.nextInt();
w[i] = in.nextInt();
}
//背包不装满情况
int ret1 = notFilled();
//背包装满情况
int ret2 = filled();
//打印结果
System.out.println(ret1);
System.out.println(ret2);
}
private static int notFilled(){
//初始化dp表，dp[i][j]表示从前i个物品中的所有选法中体积不超过j的最大价值
//空间优化一：一维数组
int [] dp = new int[capacity+1];
//我们无需初始化，因为对于边界情况，比如第一列，我们填表的时候会进行特殊判断
//同时对于第一行，没有选择物品最大价值肯定是0嘛
//——————————————状态转移方程推导———————————————————
//如果我们不选当前i物品，那我们直接dp[i-1][j]
//如果我们选择一个i物品，则为dp[i-1][j-v[i]]+w[i]
//如果我们选择两个i物品，则为dp[i-1][j-2v[i]]+2w[i]
//.........
//如果我们选择k个i物品（不超过背包容量），则为dp[i-1][j-kv[i]]+kw[i]
//—————————————————————————————————————————————————
//如果我们进行等价替换，把dp[i][j]中j-->j-v[i]，则方程变为
//dp[i-1][j-v[i]] dp[i-1][j-2v[i]]+w[i] ......... dp[i-1][j-kv[i]]+(k-1)w[i]
//发现没有，我们如果进行等价替换，dp[i][j-v[i]]就包括了dp[i][j]从dp[i][j-v[i]]+w[i]开始后面的值
//并且只相差一个w[i]，我们直接加上就好了
//因此我们最终的状态转移方程是Math.max(dp[i-1][j],dp[i][j-v[i]]+w[i])
for(int i = 1;i <= count;i++){
//常数时间优化：从左向右填表，并且不从0开始填表
for(int j = v[i];j <= capacity;j++){
dp[j] = Math.max(dp[j],dp[j-v[i]]+w[i]);
}
}
return dp[capacity];
}
private static int filled(){
int [] dp = new int[capacity+1];
//初始化，对于第一列我们不用管，因为我们填表会进行判断
//但是对于第一行，第一个位置是0，因为我们没有选物品体积为0就是0
//但是从下一个开始，我们为了区分究竟是不存在状态还是初始化状态
//-1表示这个状态不存在，0就表示默认
for(int i = 1;i <= capacity;i++){
//常数时间优化：配合填表形成无限小的数
dp[i] = -0x3f3f3f3f;
}
for(int i = 1;i <= count;i++){
for(int j = v[i];j <= capacity;j++){
//为什么可以简化if判断？因为如果dp[j-v[i]]+w[i]结果足够小，比-1还小，最终结果还是dp[j]
dp[j] = Math.max(dp[j],dp[j-v[i]]+w[i]);
}
}
return dp[capacity] < 0 ? 0 : dp[capacity];
}
}
发表于 2026-01-14 17:34:41
回复(0)
1. 使用dp表进行分析, 理解dp表的含义。mem[ix][jx] 表示 包容量是jx时候，装下ix个物品时，表示的最大价值
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX(x, y) ((x) > (y) ? (x) : (y))
int get_dp_value(int** mem, int cnt, int tgt, int* w, int* v) {
for (int ix = 1; ix <= cnt; ix++) {
for (int jx = 1; jx <= tgt; jx++) {
if (jx < w[ix])
mem[ix][jx] = mem[ix-1][jx];
else
mem[ix][jx] = MAX(mem[ix-1][jx], v[ix]+mem[ix][jx - w[ix]]);
}
}
return mem[cnt][tgt];
}
int main() {
int cnt = 0, tgt = 0, val = 0;
scanf("%d %d", &cnt, &tgt);
int w[cnt+1], v[cnt+1];
for (int ix = 1; ix <= cnt; ix++)
scanf("%d %d", &w[ix], &v[ix]);
int **mem = malloc((cnt + 1) * sizeof(*mem));
for (int ix = 0; ix <= cnt; ix++) {
mem[ix] = malloc((tgt + 1) * sizeof(int));
}
// 设置初值
memset(mem[0], 0, sizeof(int) * (tgt + 1));
for (int ix = 1; ix <= cnt; ix++)
mem[ix][0] = 0;
val = get_dp_value(mem, cnt, tgt, w, v);
printf("%d\n", val);
// 设置初值
for (int ix = 0; ix <= cnt; ix++)
mem[ix][0] = 0;
for (int ix = 1; ix <= tgt; ix++)
mem[0][ix] = INT_MIN;
val = get_dp_value(mem, cnt, tgt, w, v);
printf("%d\n", val < 0 ? 0 : val);
return 0;
}
2. 将dp 表进行简化
#include <stdio.h>
#include <limits.h>
#define MAX(x, y) ((x) > (y) ? (x) : (y))
int get_dp_value(int* mem, int cnt, int tgt, int* w, int* v) {
for (int ix = 1; ix <= cnt; ix++)
for (int jx = w[ix]; jx <= tgt; jx++)
mem[jx] = MAX(mem[jx], v[ix] + mem[jx - w[ix]]);
return mem[tgt];
}
int main() {
int cnt = 0, tgt = 0, val = 0;
scanf("%d %d", &cnt, &tgt);
int w[cnt+1], v[cnt+1];
for (int ix = 1; ix <= cnt; ix++)
scanf("%d %d", &w[ix], &v[ix]);
int mem[tgt + 1];
memset(mem, 0, sizeof(int) * (tgt + 1));
val = get_dp_value(mem, cnt, tgt, w, v);
printf("%d\n", val);
for (int ix = 1; ix <= tgt; ix++)
mem[ix] = INT_MIN;
mem[0] = 0;
val = get_dp_value(mem, cnt, tgt, w, v);
printf("%d\n", val < 0 ? 0 : val);
return 0;
}
发表于 2025-01-20 02:11:35
回复(0)
#include <stdio.h>
#include <limits.h>
int max(int a, int b) {
return (a > b ? a : b);
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
int v[n + 1], w[n + 1], dp[n + 1][m + 1];
v[0] = 0, w[0] = 0;
for (int i = 0; i <= m; i++) {
dp[0][i] = 0;
}
for (int i = 1; i <= n; i++) {
dp[i][0] = 0;
scanf("%d %d", &v[i], &w[i]);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (j<v[i]) {
dp[i][j]=dp[i - 1][j];
}
else {
dp[i][j] = max(dp[i - 1][j],dp[i][j-v[i]]+w[i]);
}
}
}
printf("%d\n", dp[n][m]);
for (int i = 0; i <= n; i++) {
dp[i][0] = 0;
}
for (int i = 1; i <= m; i++) {
dp[0][i] = INT_MIN;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (j<v[i]) {
dp[i][j]=dp[i - 1][j];
}
else {
dp[i][j] = max(dp[i - 1][j],dp[i][j-v[i]]+w[i]);
}
}
}
printf("%d", (dp[n][m] > 0 ? dp[n][m] : 0));
return 0;
}
发表于 2024-12-01 11:50:16
回复(0)
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1002;
int n, V, v[N], w[N];
int dp[N];
int main() {
cin >> n >> V;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++)
for (int j = v[i]; j <= V; j++) {
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
cout << dp[V] << endl;
memset(dp, -1, sizeof(dp));
dp[0] = 0;
for (int i = 1; i <= n; i++)
for (int j = v[i]; j <= V; j++) {
if (dp[j - v[i]] != -1)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
dp[V] = (dp[V] == -1) ? 0:dp[V];
cout << dp[V] <<endl;
return 0;
}
发表于 2024-05-22 15:08:11
回复(0)
#include <climits>
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int dp[N];
int dp2[N];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i];
}
for (int i = 1; i <= m; i++) {
dp2[i] = INT_MIN;
}
for (int i = 1; i <= n; i++) {
for (int j = v[i]; j <= m; j++) {
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
dp2[j] = max(dp2[j], dp2[j - v[i]] + w[i]);
}
}
cout << dp[m] << endl;
if(dp2[m] < 0){
cout << 0 << endl;
}else{
cout << dp2[m] << endl;
}
return 0;
}
编辑于 2024-03-22 11:25:06
回复(0)
首先按0-1背包的方案来做，逆向推，每次试可以装几个同样的物品，然后发现超时，代码如下：
#include <iostream>
#include <vector>
using namespace std;
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];
}
vector<int> dp1(V+1,0), dp2(V+1, -1);
dp2[0] = 0;
for(int i=0; i<n; i++){
for(int j=V; j>=v[i]; j--){ //逆向推
int temp1 = j-v[i], temp2=w[i];
while(temp1>=0){
dp1[j] = max(dp1[j], dp1[temp1]+temp2);
if(dp2[temp1]>=0){
dp2[j] = max(dp2[j], dp2[temp1]+temp2);
}
temp1 -= v[i];
temp2 += w[i];
}
}
}
cout<<dp1[V]<<endl;
if(dp2[V]<0) cout<<0;
else cout<<dp2[V];
return 0;
} 后面发现如果正向推，就可以了，因为不同于0-1背包每件物品只能装一次。代码如下： #include <iostream>
#include <vector>
using namespace std;
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];
}
vector<int> dp1(V+1,0), dp2(V+1, -1);
dp2[0] = 0;
for(int i=0; i<n; i++){
for(int j=v[i]; j<=V; j++){//正向推
dp1[j] = max(dp1[j], dp1[j-v[i]]+w[i]);
if(dp2[j-v[i]]>=0){
dp2[j] = max(dp2[j], dp2[j-v[i]]+w[i]);
}
}
}
cout<<dp1[V]<<endl;
if(dp2[V]<0) cout<<0;
else cout<<dp2[V];
return 0;
}
发表于 2024-01-02 17:30:35
回复(0)
#include <iostream>
#include <string.h>
using namespace std;
const int N = 1010;
int n, V, v[N], w[N];
int dp[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 = v[i]; j <= V; j++)
dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
cout << dp[V] << endl;
memset(dp, 0, sizeof(dp));
for (int j = 1; j <= V; j++)
dp[j] = -1;
for (int i = 1; i <= n; i++)
{
for (int j = v[i]; j <= V; j++)
{
if(dp[j-v[i]] != -1)
dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
}
}
cout << (dp[V] == -1 ? 0 : dp[V]) << endl;
return 0;
}
发表于 2023-09-04 13:53:59
回复(0)
# 输入的个数和总背包的体积
n ,V = map(int,input().split(' '))
#构造两个列表用来放物品和对应的价值
v,w = [],[]
for i in range(n):
l = list(map(int,input().split(' ')))
v.append(l[0])
w.append(l[1])
#g构造一个dp用来放数据
dp1=[0 for i in range(V+1)]
dp2=[float('-inf') for i in range(V+1)]
dp2[0] = 0
#循环取每一个物品和对应的背包的容量,由于数量任意多个，不能采取逆序的方式
for i in range(n):
for j in range(V+1):
if j>=v[i]:
dp1[j] = max(dp1[j],dp1[j-v[i]]+w[i])
dp2[j] = max(dp2[j],dp2[j-v[i]]+w[i])
print(dp1[V])
res = 0 if dp2[-1]==float('-inf') else dp2[-1]
print(res)
n ,V = map(int,input().split(' '))
#构造两个列表用来放物品和对应的价值
v,w = [],[]
for i in range(n):
l = list(map(int,input().split(' ')))
v.append(l[0])
w.append(l[1])
#g构造一个dp用来放数据
dp1=[0 for i in range(V+1)]
dp2=[float('-inf') for i in range(V+1)]
dp2[0] = 0
#循环取每一个物品和对应的背包的容量,由于数量任意多个，不能采取逆序的方式
for i in range(n):
for j in range(V+1):
if j>=v[i]:
dp1[j] = max(dp1[j],dp1[j-v[i]]+w[i])
dp2[j] = max(dp2[j],dp2[j-v[i]]+w[i])
print(dp1[V])
res = 0 if dp2[-1]==float('-inf') else dp2[-1]
print(res)
发表于 2022-08-27 09:58:30
回复(0)
#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=w[i];j<=weight;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=w[i];j<=weight;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';
}
#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=w[i];j<=weight;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=w[i];j<=weight;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:58:39
回复(0)
下面的代码为什么是80%通过率的，没想明白
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
int num = in.nextInt();
int bagW = in.nextInt();
int[] array = new int[bagW+1];
int[] array1 = new int[bagW+1];
for(int j=bagW;j>0;j--){
array1[j]=Integer.MIN_VALUE;
}
for(int i=1;i<=num;i++){
int w = in.nextInt();
int v = in.nextInt();
for(int j=bagW;j>=0;j--){
int max = array[j];
int max1 = array1[j];
for(int k=1;k*w<=j;k++){
max=Math.max(array[j-k*w]+k*v,array[j]);
max1=Math.max(array1[j-k*w]+k*v,array1[j]);
}
array[j]=max;
array1[j]=max1;
}
}
System.out.println(array[bagW]);
if(array1[bagW]<0){
array1[bagW]=0;
}
System.out.println(array1[bagW]);
}
}
发表于 2022-05-27 16:44:47
回复(0)
#include<iostream>
#include<cstdio>
#include<climits>
using namespace std;
const int N = 1000 + 10;
int v[N], w[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 = w[i]; j <= m; 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:55:55
回复(0)
import sys
# 空间复杂度使用二维数组
def ks(n, V, P, M):
dp = [[float("-inf") for _ in range(V+1)] for _ in range(n+1)]
for x in range(len(dp)):
dp[x][0] = 0
# for y in range(len(dp[0])):
# dp[0][y] = 0
for i in range(1, n+1):
for j in range(1, V+1):
if j >= P[i]:
for k in range(0, j//P[i]+1):
dp[i][j] = max(dp[i][j], dp[i-1][j-k*P[i]]+k*M[i])
else:
dp[i][j] = dp[i-1][j]
print(max(max(dp)))
if dp[-1][-1] == float("-inf"):
print(0)
else:
print(dp[-1][-1])
# 通过19/20，算法超时
def ks_B(n, V, P, M):
dp = [float("-inf") for _ in range(V+1)]
dp[0] = 0
for i in range(1, n+1):
for j in range(V, -1, -1):
for k in range(0, j//P[i]+1):
dp[j] = max(dp[j], dp[j-k*P[i]]+k*M[i])
print(max(dp))
if dp[-1] != float("-inf"):
print(dp[-1])
else:
print(0)
return
# 满足要求
# 思考：容量序列遍历为何可以使用正向序列？而且序列的起点可以为P[i]?
# 完全背包问题，物品i没有数量限制;
# 当 j < P[i]时，容量不足以容纳物品 i，
# 相当于d[i][j] = d[i-1][j], 在O(n)复杂度的算法中也就是不更新内容，所以可以设置起点为P[i]
def ks_C(n, V, P, M):
dp = [float("-inf") for _ in range(V+1)]
dp[0] = 0
for i in range(1, n+1):
for j in range(P[i], V+1):
dp[j] = max(dp[j], dp[j-P[i]]+M[i])
print(max(dp))
if dp[-1] != float("-inf"):
print(dp[-1])
else:
print(0)
return
line1 = [int(x) for x in sys.stdin.readline().split()]
n = line1[0]
V = line1[1]
P = [0]
M = [0]
for line in sys.stdin:
tmp = [int(x) for x in line.split()]
P.append(tmp[0])
M.append(tmp[1])
ks_C(n, V, P, M)
发表于 2021-11-08 15:00:36
回复(0)
补一个python3，与前一个背包问题的区别在于调整了dp循环顺序，从容量1到容量n进行循环，这样后续的dp就可以用到之前用过的物品
def ans():
n, size = map(int,input().split(" "))
v, w = [] , []
for _ in range(n):
t1, t2 = map(int,input().split(" "))
v.append(t1)
w.append(t2)
dp1 = [0] * (size+1)
dp2 = [float("-inf")] * (size+1)
dp2[0] = 0
for i in range(n):
for j in range(1,size+1):
if j >= v[i]:
dp1[j] = max(dp1[j], dp1[j-v[i]] + w[i])
dp2[j] = max(dp2[j], dp2[j-v[i]] + w[i])
print(dp1[-1])
print(dp2[-1] if dp2[-1] != float("-inf") else 0)
ans()
发表于 2021-11-08 13:30:35
回复(0)
问题信息
难度：
16条回答
157收藏
1473浏览
通过挑战的用户
查看代码-
2023-02-07 09:03:53 -
2022-09-16 13:50:38 -
2022-09-16 10:05:17 -
2022-09-15 21:24:19 -
2022-09-15 20:15:41
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
