2022 ICPC杭州站 C(01背包，简单dp)

题目
题意: 给定n个物品，体积为vi，其体积t∈1-vi分别对应一个价值wi,t。背包容量上限为k，若某个物品能放入背包，则必须完全放入；可以选择至多一个个物品作为特殊物品，其可以部分放入。
思路: 由于每个物品的体积很小，至多为10.可以采用n * k * vi的dp方式. f[i][j][k]表示从前i个物品中选，体积为j且是否存在部分选择的物品。(k=1表示已经选择了某个物品部分选择，k=0反之亦然)
PS: 注意将dp数组初始化为-INF，这样才能保证第二维里是恰好用了体积为j的物品.
代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 3100;
int f[N][N][2];
int v[N];
int w[N][11];
int n,m,k,T;
void solve()
{
cin>>n>>k;
int sum = 0;
for(int i=1;i<=n;++i)
{
cin>>v[i];
sum += v[i];
for(int j=1;j<=v[i];++j)
{
cin>>w[i][j];
}
}
if(sum<=k)
{
int ans = 0;
for(int i=1;i<=n;++i) ans += w[i][v[i]];
cout<<ans;
return ;
}
memset(f,-0x3f,sizeof(f));
f[0][0][0] = 0;
for(int i=1;i<=n;++i)
{
for(int j=0;j<=k;++j)
{
f[i][j][0] = f[i-1][j][0];
f[i][j][1] = f[i-1][j][1]; //前i个物品中选过部分 
if(j>=v[i])
{
f[i][j][0] = max(f[i][j][0],f[i-1][j-v[i]][0]+w[i][v[i]]); //不选部分
f[i][j][1] = max(f[i][j][1],f[i-1][j-v[i]][1]+w[i][v[i]]); //选过部分 
}
for(int dx=1;dx<v[i];++dx)
{
if(j-dx>=0) f[i][j][1] = max(f[i][j][1],f[i-1][j-dx][0]+w[i][dx]); //当前选部分	
}
}
}
int ans = f[n][k][0];
ans = max(ans,f[n][k][1]);
cout<<ans;
}
signed main(void)
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
solve();
return 0;
}

最后

以上就是殷勤大炮为你收集整理的2022 ICPC杭州站 C(01背包，简单dp)的全部内容，希望文章能够帮你解决2022 ICPC杭州站 C(01背包，简单dp)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。