问题标题: 酷町堂：1210西瓜问题怎么做（求思路）（急）

Question

0

已解决

高翊天

初级守护

#include<iostream>
using namespace std;
int n;
int w[100];
long long s;
int f[1000000];
int main()
{
   cin>>n;
   for (int i=1;i<=n;i++)
   {
       cin>>w[i];
       s+=w[i];
   }
   int s1=s/2;
   for (int i=1;i<=n;i++)
   {
       for (int v=s1;v>=w[i];v--)
       {
           f[v]=max(f[v-1],f[v-w[i]]+w[i]);
       }
   }
   cout<<s-2*f[s1];
}

Answer 1

已采纳

黄俊博

资深光能

核心如下：
int v=sum/2;
    for (int i=1;i<=n;i++)
    {
        for (int j=v;j>=w[i];j--)
        {
             f[j]=max(f[j],f[j-w[i]]+c[i]);
        }
    }
    cout<<sum-2*f[v];

注意前面还要把输入的w累加，且c[i]=w[i];

懂吗？？

Answer 2

朱小川

缔造者

同上

Answer 3

王星河

资深光能

01背包

Answer 4

吴峻逸

初级守护

你的动态转移方程写错了，应该如下：

f[v]=max(f[v],f[v-w[i]]+w[i]);

Answer 5

储金洋

新手光能

动态转移方程错了，应是：

f[v]=max(f[v],f[v-w[i]]+w[i]);

Answer 6

程之行

高级守护

 for i:=1 to n do
        for j:=v downto s[i] do 
        begin
            if f[j-s[i]] + c[i] > f[j] then
                f[j]:=f[j-s[i]] + c[i];
        end;
        writeln(sum-f[v]-f[v]);
end.

可以用一维写上面一样

Answer 7

张瑀涵

高级光能

f[v]=max(f[v-1],f[v-w[i]]+w[i])

改成

f[v]=max(f[v],f[v-w[i]]+w[i])

Answer 8

杨陈卓

新手天翼

动态转移方程错

    for(int i=1;i<=n;i++)
        for(int j=m;j>=k[i];j--)
            f[j]=max(f[j],f[j-k[i]]+k[i]);

Answer 9

王子凡

高级光能

动态转移方程错了

应该是f[v]=max(f[v]...);

问题标题: 酷町堂：1210西瓜问题怎么做（求思路）（急 ）

9 个回答:

问题标题: 酷町堂：1210西瓜问题怎么做（求思路）（急）