0
已解决
初级守护
#include<iostream>
using namespace std;
int w[2100],c[2100],n,m,f[2100][2100];
int main()
{
cin>>n>>m;
cin>>w[1]>>c[1];
int j=1;
while (w[j]!=0&&c[j]!=0)
{
j++;
cin>>w[j]>>c[j];
}
for (int i=1;i<=n;i++)
{
for (int v=m;v>=0;v--)
{
if (w[i]<=v)
f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i]);
else f[i][v]=f[i-1][v];
}
}
cout<<f[n][m];
}
0
已采纳
资深守护
你的题目意思理解错了
题目是说有多组测试数据
是指有多组n和m的情况，所以是判断n和m是否都等于0，不是指c和w为0
对于每一组的n和m，我们输入c和w进行运算来判断此时能放入背包的黄金的总价值。
0
缔造者
背包
0
高级光能
和01背包基本一模一样
for (int i=1;i<=n;i++)
{
for (int j=1;j<=v;j++)
{
if (j>=w[i])
{
f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i]);
}
else
{
f[i][j]=f[i-1][j];
}
}
}
核心代码
王子凡在2018-02-07 10:13:39追加了内容
f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i])
是01背包的动态转移方程
f[i-1][j]表示不选第i个f[i-1][j-w[i]]+c[i]表示选第i个
f[i][j]表示前i件物品放入一个容量为j的背包可以获得的最大价值
0
资深天翼
dp背包大法好。
while(!(n==0&&m==0))
{
memset(f,0,sizeof(f));
for(int i=1; i<=n; i++)
cin>>w[i]>>c[i];
for(int i=1; i<=n; i++)
{
for(int j=m; j>=w[i]; j--)
f[j]=max(f[j],f[j-w[i]]+c[i]);
}
cout<<f[m]<<endl;
cin>>n>>m;
}
直接套用状态转移方程。
0
高级守护
直接用背包，我没判断也过了
