二维数组的背包问题andSDNUOJ1061采药3

每个价值为v[i]的物品都有两个代价a[i]（最大为A）和b[i]（最大为B）

可以把dp数组写成三维

dp[i][j][k]表示前i件物品在付出代价为j和k时可获得的最大价值

状态转移方程dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-a[i]][k-b[i]])

01背包----j,k逆序循环

for(int i = 1; i <= n; i++) { for(int j = A; j >= a[i]; j--) { for(int k = B; k >= b[i]; k--) { dp[j][k] = max(dp[j][k], dp[j-a[i]][k-b[i]]+v[i]); } } }

SDNUOJ1061采药3

Description

XXX上山去采药。XXX有一个最大承重为m(1<=m<=100)且容积为t(1<= t<=100)的背包，他所采集的药材的总重量不能大于背包的最大承重且总体积不能大于背包的容积。已知共有n(1<=n<=1000)株药材，并且知道每株药材的重量w1(1<=w1<=m)、体积w2(1<=w2<=t)及价值v(1<=v<=100000)，如何选择，才能使得采到的药材的总价值最大？

Input

第1行为三个整数m、t和n，分别为背包的最大承重、容积及药材的数量。 第2至n+1行每行三个整数w1、w2和v，分别表示每株药材的重量、体积及价值。

Output

能采到的药材的最大总价值

代码

#include<cstring> #include<iostream> #include<algorithm> using namespace std; int main() { int m, t, n; int w1[1010]; int w2[1010]; int v[1010]; int dp[110][110]; cin>>m>>t>>n; for(int i = 1; i <= n; i++) { cin>>w1[i]>>w2[i]>>v[i]; } memset(dp, 0, sizeof(dp)); for(int i = 1; i <= n; i++) for(int j = m; j >= w1[i];j--) for(int k = t;k >= w2[i]; k--) dp[j][k] = max(dp[j][k], dp[j-w1[i]][k-w2[i]]+v[i]); cout<<dp[m][t]<<endl; return 0; }

完全背包----j,k顺序循环

多重背包----把物品拆分成01背包的样子