题目：
一个旅行者有一个最多能装 M 公斤的背包，现在有 nn 件物品，它们的重量分别是W1，W2，...,Wn它们的价值分别为C1,C2,...,Cn求旅行者能获得最大总价值。
第一行：两个整数，MM(背包容量，M≤200)和NN(物品数量，N≤30)；
第2..N+12..N+1行：每行二个整数Wi，CiWi，Ci，表示每个物品的重量和价值。
仅一行，一个数，表示最大总价值。
10 4 2 1 3 3 4 5 7 9
12
这类问题就是01背包问题，是dp背包中的最简单的一种
状态转移方程：f[i][v]=max(f[i-1][v],f[i-1][v-c[i]]+w[i])
即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。
将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]（来自百度）
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<queue> #include<stack> #include<vector> #include<map> #include<string> #include<cstring> using namespace std; const int maxn=999999999; const int minn=-999999999; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < ‘0‘ || c > ‘9‘) { if(c == ‘-‘) f = -1; c = getchar(); } while(c >= ‘0‘ && c <= ‘9‘) x = x * 10 + c - ‘0‘, c = getchar(); return x * f; } int f[1005][1050],c[1050],w[1050],m,n; int main() { cin>>m>>n; for(int i=1; i<=n; ++i) { cin>>w[i]>>c[i]; } for(int i=1; i<=n; ++i) { for(int v=m; v>0; v--) { if(w[i]<=v) { f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i]); } else { f[i][v]=f[i-1][v]; } } } cout<<f[n][m]; return 0; }
问题来了开一个二维数组是不是有点浪费空间（想想蛇形填数那个题，二维数组开不到那么大，就GG了）所以只需要用f[v]表示重量不超过v的最大价值就OK了
f[i]=max(f[v],f[v-c[i]]+w[i])
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<queue> #include<stack> #include<vector> #include<map> #include<string> #include<cstring> using namespace std; const int maxn=999999999; const int minn=-999999999; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < ‘0‘ || c > ‘9‘) { if(c == ‘-‘) f = -1; c = getchar(); } while(c >= ‘0‘ && c <= ‘9‘) x = x * 10 + c - ‘0‘, c = getchar(); return x * f; } int f[1050],c[1050],w[1050],m,n; int main() { cin>>m>>n; for(int i=1; i<=n; ++i) { cin>>w[i]>>c[i]; } for(int i=1; i<=n; ++i) { for(int v=m; v>0; v--) { if(w[i]<=v) { f[v]=max(f[v],f[v-w[i]]+c[i]); } else { f[v]=f[v]; } } } cout<<f[m]; return 0; }
设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。
第一行：两个整数，M(背包容量，M≤200)和N(物品数量，N≤30)；
第2..N+1行：每行二个整数Wi,Ci，表示每个物品的重量和价值。
仅一行，一个数，表示最大总价值。
10 4 2 1 3 3 4 5 7 9
max=12
特点：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
原文：https://www.cnblogs.com/pyyyyyy/p/10775620.html