对于每个物品,如果购买,价值为A[i]*x+B[i]的背包问题。
先写了一发是WA的= =。代码如下:
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <set>
using namespace std;
typedef pair<int,int> pii; pii dp[];
int w[],A[],B[]; int main()
{
int T;scanf("%d",&T);
while(T--)
{
int m,n;scanf("%d%d",&m,&n);
for(int i=;i<=n;i++) scanf("%d%d%d",w+i,A+i,B+i);
for(int i=;i<=m;i++) dp[i] = pii(,);
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++) dp[j] = pii(dp[j].first, );
for(int j=w[i];j<=m;j++)
{
if(dp[j-w[i]].first + A[i] + (dp[j-w[i]].second == ? B[i] : ) > dp[j].first)
{
dp[j].first = dp[j-w[i]].first + A[i] + (dp[j-w[i]].second == ? B[i] : );
dp[j].second = ;
}
}
}
printf("%d\n",dp[m].first);
}
return ;
}
正解是,先跑一遍价值为A[i]+B[i]的01背包,再跑一遍价值为A[i]完全背包。所以上面的代码错了大概是因为,这两个背包的第二个for的方向是不同的,没办法一起跑吧(除非用另外一组变量记录下到前一个为止的dp值,然后就可以同时跑了)。。对背包问题的理解还是不够深啊。。
————————————————————————————————————————————————————————
想了一下,感觉上面说的括号里的再用一个数组记录的方法貌似不太对。。虽然那份代码AC了- -。。反正跑两遍的方法肯定是对的。。我说的是这个博客里面的第二个方法:http://www.cnblogs.com/wmxl/p/4749780.html。也有可能是我对完全背包的理解不够深刻。。先放着再说好了。。
————————————————————————————————————————————————————————
AC代码如下:
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <set>
using namespace std;
typedef pair<int,int> pii; int dp[];
int w[],A[],B[]; int main()
{
int T;scanf("%d",&T);
while(T--)
{
int m,n;scanf("%d%d",&m,&n);
for(int i=;i<=n;i++) scanf("%d%d%d",w+i,A+i,B+i);
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++)
{
for(int j=m;j>=w[i];j--) dp[j] = max(dp[j], dp[j-w[i]] + A[i] + B[i]);
for(int j=w[i];j<=m;j++) dp[j] = max(dp[j], dp[j-w[i]] + A[i]);
}
printf("%d\n",dp[m]);
}
return ;
}