题解 | 【模板】完全背包
【模板】完全背包
https://www.nowcoder.com/practice/237ae40ea1e84d8980c1d5666d1c53bc
#include <bits/stdc++.h>
using namespace std;
#define N (int)(1e3+5)
int dp[N];
int dp2[N];
int value[N],volume[N];
int my_max(int a,int b){
return (a>b)?a:b;
}
int main(){
int n,V;
scanf("%d %d",&n,&V);
for(int i=0;i<n;i++){
scanf("%d %d",&volume[i],&value[i]);
}
for(int i=1;i<=V;i++){
dp2[i]=INT_MIN;
}
for(int i=0;i<n;i++)//遍历每种物品
{
//正序可以多次使用物品,累加物品
for(int j=volume[i];j<=V;j++){
dp[j]=my_max(dp[j],dp[j-volume[i]]+value[i]);
dp2[j]=my_max(dp2[j],dp2[j-volume[i]]+value[i]);
}
}
printf("%d\n",dp[V]);
if(dp2[V]>0) printf("%d\n",dp2[V]);
else printf("%d\n",0);
return 0;
}
#动态规划#
投递美团等公司6个岗位 >