赛斯石P3983(完全背包)

题目地址

本来的思路是:每个船的费用已知，每个石头的价值也已知，我直接就用相应的价值减去费用得道每个船能获得的钱，并觉得这是最大值，然后把船视为物品，need值视为背包容量直接完全背包

但是无忽略了一个问题就是船本身自己也是一个背包，不经过背包的话船是无法达到最大价值的，打个比方:容量为11的船可以装大小为4和7的石头。

所以正确思路:每个船先完全背包一次，算出每个船能运的装的最大价值，然后减去相应的路费，再把减掉路费后每个船的获利存下来视为物品，把need值视为背包容量进行完全背包。

#include 
#include 
using namespace std;
int need,obj[11],ship[11],cost[11]={0,1,3,5,7,9,10,11,14,15,17};
int dp[100010]={0};//题目经过加强，普通的完全背包MLE，只能滚动数组优化后做
int DP()
{
 for(int i=1;i<=10;i++)
 {
     for(int j=1;j<=i;j++)
     {
         ship[i]=max(ship[i],ship[i-j]+obj[j]);
     }
 }
 for(int i=1;i<=10;i++)
 {
     ship[i]-=cost[i];
 }
 for(int i=1;i<=10;i++)
 {
     for(int j=i;j<=need;j++)
     {
         dp[j]=max(dp[j],dp[j-i]+ship[i]);
     }
 }
  return dp[need];
}
int main()
{
    //freopen("in.txt","r",stdin);
    cin>>need;
    for(int i=1;i<=10;i++)
    {
        cin>>obj[i];
    }
    cout< 
记得改longlong！！
 
总结点:
 完全背包在有多个背包的情况下滚动数组,这题涉及到了多个背包的完全背包问题，就是第一次背包的那个，这个之前没见过要记一下。
 
另外看别人的代码发现了这样一种写法
 
 for(int i=1;i<=need;i++){
        for(int j=1;j<=10;j++){
            if(i-j<0){
                break;
            }
            dp[i]=max(dp[i],dp[i-j]+best[j]);
        }
    }
 
就是第一层控制背包容量，第二层控制物品。