$$\color{Red}{01背包问题:三种语言+原版和滚动数组优化}$$
这里附带打个广告——————我做的所有的题解
包括基础提高以及一些零散刷的各种各样的题
题目介绍
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值
数据范围
0 < N, V ≤ 1000
0 < vi, wi ≤ 1000
输入样例：
4 5
1 2
2 4
3 4
4 5
输出样例：
8
方法一：二维状态表示
f[i][j] = max(f[i-1][j], f[i-1][j - v[i]] + w[i]);
1. java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 1010;
static int n, m;
static int[][] f = new int[N][N];
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
String[] str1 = br.readLine().split(" ");
n = Integer.parseInt(str1[0]);
m = Integer.parseInt(str1[1]);
for (int i = 1; i <= n; i++) {
String[] str2 = br.readLine().split(" ");
int v = Integer.parseInt(str2[0]);
int w = Integer.parseInt(str2[1]);
for (int j = 0; j <= m; j++) {
f[i][j] = f[i-1][j];
if (j >= v)
f[i][j] = Math.max(f[i][j], f[i-1][j - v] + w);
}
}
System.out.println(f[n][m]);
}
}
2.python3代码
N = 1010
f = [[0] * N for i in range(N)]
w = [0] * N
v = [0] * N
n, m = map(int, input().split())
for i in range(1, n + 1):
v[i], w[i] = map(int, input().split())
# DP
for i in range(1, n + 1):
for j in range(1, m + 1):
if v[i] > j:
f[i][j] = f[i-1][j]
else:
f[i][j] = max(f[i-1][j], f[i-1][j - v[i]] + w[i])
print(f[n][m])
3.C++代码
#include <iostream>
using namespace std;
const int MAX = 1010;
int v[MAX], w[MAX];//v表示物品体积，w表示物品价值
//状态方程：f[i][j]表示前i件物品在背包体积为j的情况下的最大价值
int f[MAX][MAX];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++) scanf("%d%d", &v[i], &w[i]);
//遍历所有f[i][j]的对应最大价值
for(int i=1; i<=n; i++)//挑选物品数
for(int j=1; j<=m; j++)//状态方程的背包值
{
if(j < v[i])//当前背包装不进第i个物品（装不进是重点）
f[i][j] = f[i-1][j];
else
f[i][j] = max(f[i-1][j], f[i-1][j - v[i]] + w[i]);
}
cout << f[n][m] << endl;
return 0;
}
方法二：一维状态表示
由于我们最终所求为f[n][m]实际并不需要保存那么多的状态，只需要维持一定大小背包的最大值，那么我们不妨进行一维的状态压缩
f[j] = max(f[j], f[j - v[i]] + w[i]);
1.算法细节
- 为什么压缩之后是倒序对状态方程中背包大小进行赋值？
当我们在一层i对f[j]进行for循环更新的时候，由一维我们可知，其实应该是f[i][j] = max(f[i-1][j], f[i-1][j - v[i] ] + w[i])
但是如果我们省略其中的第一维，变成f[j] = max(f[j], f[j - v[i]] + w[i])后，如果还按从小到大刷新背包为j的状态方程值，刷新更大的jplus会使用到更小背包f[i-1][jmin]，但是可能因为我们一维压缩并没有i维度来保持是否使用这个维度,在jplus循环下调用f[i-1][jmin]的情况下，可能更小的jmin在之前已经刷新了整个状态方程的值，整个方程已经被刷新成f[i][jmin]的值了，类似Bellman_ford最短路问题出现的，我们当时运用了back事先存储好了dist的值。
如果我们倒序进行赋值，同层i下，先对更大的j进行更新，那么在调用更小的f[i-1][jmin]时，就没有把小的背包更新为f[i][jplus]，一层层慢慢再刷新到底，才更新为本层i的各背包大小，直到进入i+1的循环
1. java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 1010;
static int n, m;
static int[] f = new int[N];
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
String[] str1 = br.readLine().split(" ");
n = Integer.parseInt(str1[0]);
m = Integer.parseInt(str1[1]);
for (int i = 1; i <= n; i++) {
String[] str2 = br.readLine().split(" ");
int v = Integer.parseInt(str2[0]);
int w = Integer.parseInt(str2[1]);
for (int j = m; j >= v; j--)
f[j] = Math.max(f[j], f[j - v] + w);
}
System.out.println(f[m]);
}
}
2.python3一维代码
N = 1010
f = [0] * N
w = [0] * N
v = [0] * N
n, m = map(int, input().split())
for i in range(1, n + 1):
v[i], w[i] = map(int, input().split())
# DP
for i in range(1, n + 1):
for j in range(m, v[i] - 1, -1):
f[j] = max(f[j], f[j - v[i]] + w[i])
print(f[m])
3.C++一维代码
#include <iostream>
using namespace std;
const int MAX = 1010;
int v[MAX], w[MAX];//v表示物品体积，w表示物品价值
//状态方程：f[j]表示背包体积为j的情况下的最大价值
int f[MAX];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++) scanf("%d%d", &v[i], &w[i]);
//遍历所有f[i][j]的对应最大价值
for(int i=1; i<=n; i++)//挑选物品数
for(int j=m; j>=v[i]; j--)//正序会污染我们本想取的f[i-1][j]
{
//if(v[i] > j) f[j] = f[j]; 这里没有i作为区别，故可以省略
//else
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
cout << f[m] << endl;
return 0;
}
