1、问题描述
有 N N N种物品和一个容量是 V V V的背包，每种物品都有无限件可用。第 i i i种物品的体积是 v i v_i vi，价值是 w i w_i wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
2、代码实现 1、二维朴素写法
#include#include#define N 1010int n, m;//n为物品个数，m为背包总容量int v[N], w[N];//分别表示体积和重量int f[N][N];//状态函数，f[i][j]表示只考虑前i个物品且体积不超过j的最大价值int main(){printf("请输入物品个数和背包容量（中间用空格隔开）：");scanf_s("%d %d", &n, &m);printf("n请输入物品体积和价值（中间用空格隔开）：n");for(int i = 1; i <= n; i++)scanf_s("%d %d", &v[i], &w[i]);for(int i = 1; i <= n; i++)for(int j = 0; j <= m; j++){//完全背包二维只能正序更新，0/1背包二维更新正序/逆序都可以f[i][j] = f[i - 1][j];//不选择第i个物品时if(j >= v[i])//如果j>=v[i]，才能选择第i个物品f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);}printf("最大价值为：%d", f[n][m]);return 0;}
完全背包二维之所以只能正序更新，不能逆序更新是因为： f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , f [ i ] [ j − v [ i ] ] + w [ i ] ) f[i][j]=max(f[i−1][j],f[i][j−v[i]]+w[i]) f[i][j]=max(f[i−1][j],f[i][j−v[i]]+w[i])想求 f [ i ] [ j ] f [ i ] [ j ] f[i][j]f[i][j] f[i][j]f[i][j]，要先求 f [ i ] [ j − v [ i ] ] f[i][j−v[i]] f[i][j−v[i]]，两者都是 f [ i ] f[i] f[i]，也就是在同一层，所以只能正序更新。
01背包二维之所以 正序逆序都可以是因为： f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − v [ i ] ] + w [ i ] ) f[i][j]=max(f[i−1][j],f[i−1][j−v[i]]+w[i]) f[i][j]=max(f[i−1][j],f[i−1][j−v[i]]+w[i])想求 f [ i ] [ j ] f[i][j] f[i][j]，要先求 f [ i − 1 ] [ j − v [ i ] ] f[i−1][j−v[i]] f[i−1][j−v[i]]，前者是 f [ i ] f[i] f[i]，后者是 f [ i − 1 ] f[i - 1] f[i−1]，不在同一层，所以 正序逆序更新都可以。
2、一维优化写法
#include#include#define N 1010int n, m;//n为物品个数，m为背包总容量int v[N], w[N];//分别表示体积和重量int f[N];//状态函数，f[j]表示只考虑前i个物品且体积不超过j的最大价值int main(){printf("请输入物品个数和背包容量（中间用空格隔开）：");scanf_s("%d %d", &n, &m);printf("n请输入物品体积和价值（中间用空格隔开）：n");for(int i = 1; i <= n; i++)scanf_s("%d %d", &v[i], &w[i]);for(int i = 1; i <= n; i++)for(int j = v[i]; j <= m; j++){//完全背包二维只能正序更新，0/1背包二维更新正序/逆序都可以f[j] = max(f[j], f[j - v[i]] + w[i]);}printf("最大价值为：%d", f[m]);return 0;}
3、进一步优化
#include#include#define N 1010int n, m;//n为物品个数，m为背包总容量int v, w;//分别表示体积和重量int f[N];//状态函数，f[j]表示只考虑前i个物品且体积不超过j的最大价值int main(){printf("请输入物品个数和背包容量（中间用空格隔开）：");scanf_s("%d %d", &n, &m);for(int i = 1; i <= n; i++){printf("n请输入物品体积和价值（中间用空格隔开）：");scanf_s("%d %d", &v, &w);for(int j = v[i]; j <= m; j++){//完全背包二维只能正序更新，0/1背包二维更新正序/逆序都可以f[j] = max(f[j], f[j - v] + w);}}printf("最大价值为：%d", f[m]);return 0;}