宠物小精灵之收服 （二维01背包）

【题目链接】

　　　　http://noi.openjudge.cn/ch0206/4978/

【算法】

　　　　做的第一道二维的背包问题，只需开的数组增加一维以正确表述每一个状态即可。本质还是多过程决策+最优子结构+无后效性。

【代码】

1 #include <bits/stdc++.h> 2 using namespace std; 3 int n,m,k,i,j,t,minm; 4 int v[1010],u[510],dp[1010][510]; 5 int main() 6 { 7 scanf("%d%d%d",&n,&m,&k); 8 minm=m; 9 for(i=1;i<=k;i++) scanf("%d%d",&v[i],&u[i]); 10 for(i=1;i<=k;i++) 11 for(j=n;j>=v[i];j--) 12 for(t=m;t>=u[i];t--) 13 dp[j][t]=max(dp[j][t],dp[j-v[i]][t-u[i]]+1); 14 for(i=0;i<=n;i++) 15 for(j=0;j<=m;j++) 16 if(dp[i][j]==dp[n][m]&&j<minm) minm=j; 17 printf("%d %dn",dp[n][m],m-minm); 18 return 0; 19 }

相关知识

[01背包] 宠物小精灵之收服(01背包+二维费用背包+思维)
【c语言】宠物小精灵之收服 [二维费用背包]
动态规划——1292：宠物小精灵之收服（二维背包问题）
AcWing 1022. 宠物小精灵之收服
宠物小精灵收服策略：01背包算法与体力优化
4102:宠物小精灵之收服
T1292：宠物小精灵之收服
宠物小精灵之收服 01背包 POJ4102
宠物小精灵之收服（二维背包）
【背包DP】【OpenJudge4978】宠物小精灵之收服

网址: 宠物小精灵之收服 （二维01背包） https://www.mcbbbk.com/newsview818650.html