|
题目大意：N个碟片中选M个，总时间不能超过L，求最大价值 题目
有好几个不大明白的地方：
1、一开始用三维，总是只能拿10、20分，我估计原因是从i到i+1个物品的传递没有做好。（以后碰到二维背包就用倒序降维方法做吧，避免出错）
2、初始化dp[j][1]会出错。后来想到dp[j][1]是存储了上一个维度的值，不可以初始化。（除非三维）
背包问题整理如下：
一维01背包问题通解：
for i=1..N
for v=V..0
{
f[v]=max{f[v],f[v-c[i]]+w[i]};
if (f[v]==f[v-c[i]]+w[i]) g[i,v]=1;//若f[v]选择后一项（输出用）
}
01背包问题输出：
i=N
v=V
while(i>0)
{
if(g[i][v]==0)
print "未选第i项物品"
else if(g[i][v]==1)
print "选了第i项物品"
v=v-c[i]
}
01背包求方案总数
初始化：f[0][0]=1;
f[i][v]+=f[i-1][v-c[i]];
01背包求最优方案总数：
for i=1..N
for v=0..V
{
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
g[i][v]=0
if(f[i][v]==f[i-1][v])
g[i][v]+=g[i-1][v];
if(f[i][v]==f[i-1][v-c[i]]+w[i])
g[i][v]+=g[i-1][v-c[i]];
}
一维完全背包问题通解：
for i=1..N
for v=0..V
f[v]=max{f[v],f[v-c[i]]+w[i]};
分组背包问题（k个组，每组要么取一个要么不取）
for k=1...K
for v=V...0
for item in group k
f[v]=max{f[v],f[v-c[i]]+w[i]};
本题ac代码：
#include<iostream>
#include<string.h>
using namespace std;
int c[101],w[101],dp[1001][101];
int main()
{
int N,M,L,i,j,k,ans=0;
cin>>N;cin>>M;cin>>L;
for (i=1;i<=N;i++)
cin>>c[i]>>w[i];
memset(dp,-1,sizeof(dp));
dp[0][0]=0;
for (i=1;i<=N;i++)
for (j=L;j>=c[i];j--)
{
// dp[j][1]=w[i];//删了这个就对了
for (k=1;k<=i;k++)
if (dp[j-c[i]][k-1]!=-1 )
dp[j][k]=max(dp[j][k],dp[j-c[i]][k-1]+w[i]);
ans=max(ans,dp[j][M]);
}
cout<<ans;
return 0;
}
| 
转播
