背包问题小结
1.体积最多是j(普通的背包) 全部初始化为0 要保证j-v[i]大于0
2.体积恰好是j dp[0]=0 dp[i]=INF j-v[i]>0
3.体积至少是j dp[0]=0 dp[i]=INF 不用管体积
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f
const int N=22,M=80;
int n,m,k;
int dp[N][M];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
cin>>n>>m>>k;
memset(dp,0x3f,sizeof dp);
dp[0][0]=0;
for(int i=1;i<=k;i++)
{
int v1,v2,w;
cin>>v1>>v2>>w;
for(int j=n;j>=0;j--)
for(int r=m;r>=0;r--)
dp[j][r]=min(dp[j][r],dp[max((int)0,j-v1)][max((int)0,r-v2)]+w);
}
cout<<dp[n][m]<<endl;
return 0;
}