题目
有N种物品和一个容量为m的背包，每种物品都有无限件可用。
第i种物品的体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。
状态转移方程f[m]=max(f[i-w[j]]+c[j],f[i])
代码如下
#include<iostream>
using namespace std;
int main(void)
{
int w[101],c[101],n,m,f[101]={0},temp;//n种 mkg背包
cin>>m>>n;
int i,j;
for(i=1;i<=n;i++)
cin>>w[i]>>c[i];
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
if(i>=w[j])
f[m]=max(f[i-w[j]]+c[j],f[i]);
}
cout<<f[m];
return 0;
}
优化代码：
#include<iostream>
using namespace std;
int main(void)
{
int w,c,n,m,f[101]={0},temp;//n种 mkg背包
cin>>m>>n;
int i,j;
for(i=1;i<=n;i++)
{
cin>>w>>c;
for(j=w;j<=m;j++)
f[j]=max(f[j-w]+c,f[j]);
}
cout<<f[m];
return 0;
}
/*int main(void)
{
long long date1,date2;
cin>>date1>>date2;
return 0;
} */附上运行图
转载请注明原文地址: https://ju.6miu.com/read-969340.html
